Mod de potencia 2 en operadores bit a bit?

Question

1. ¿Cómo funciona la mod de potencia de 2 solo en bits de orden inferior de un número binario (1011000111011010)?
2. ¿Qué es este número mod 2 para potencia 0, 2 para potencia 4?
3. ¿Qué tiene que ver la potencia de 2 con el operador de módulo? ¿Tiene una propiedad especial?
4. ¿Puede alguien darme un ejemplo?

El instructor dice "Cuando tomas algo mod a la potencia de 2, simplemente tomas sus bits de orden inferior". Tenía demasiado miedo de pedir lo que quería decir =)

Answer 1

quería decir que la toma de number mod 2^n es equivalente a despojarse de todos, pero los n más bajo orden (más a la derecha-) bits de number.

Por ejemplo, si n == 2,

number  number mod 4 
00000001  00000001 
00000010  00000010 
00000011  00000011 
00000100  00000000 
00000101  00000001 
00000110  00000010 
00000111  00000011 
00001000  00000000 
00001001  00000001 
etc. 

Así, en otras palabras, number mod 4 es la misma que number & 00000011 (donde & significa bit a bit-y)

---

en cuenta que esta obra exactamente lo mismo en base-10: number mod 10 le da el último dígito del número en base-10, number mod 100 le da los últimos dos dígitos, etc.

Answer 2

Lo que quiere decir es que:

x modulo y = (x & (y − 1)) 

Cuando y es una potencia de 2.

Ejemplo:

0110010110 (406) modulo 
0001000000 (64) = 
0000010110 (22) 
^^^^<- ignore these bits 

Uso su ejemplo ahora:

1011000111011010 (45530) modulo 
0000000000000001 (2 power 0) = 
0000000000000000 (0) 
^^^^^^^^^^^^^^^^<- ignore these bits 

1011000111011010 (45530) modulo 
0000000000010000 (2 power 4) = 
0000000000001010 (10) 
^^^^^^^^^^^^<- ignore these bits 

Answer 3

Considera cuando tomas un módulo de número 10. Si lo haces, obtienes el último dígito del número.

334 % 10 = 4 
    12345 % 10 = 5 

Del mismo modo, si toma un número de módulo 100, solo obtiene los dos últimos dígitos.

334 % 100 = 34 
    12345 % 100 = 45 

Así que puede obtener el módulo de una potencia de dos mirando sus últimos dígitos en binario. Eso es lo mismo que hacer un bitwise y.

Answer 4

El módulo en general devuelve el resto de un valor después de la división. Por lo tanto, x mod 4, por ejemplo, devuelve 0, 1, 2 o 3 según x. Estos valores posibles se pueden representar utilizando dos bits en binario (00, 01, 10, 11) - otra forma de hacerlo es x mod 4 es simplemente establecer todos los bits a cero en x, excepto los dos últimos.

Ejemplo:

 x = 10101010110101110 
x mod 4 = 00000000000000010 

Answer 5

Responder a sus preguntas específicas:

1. mod es un operador de resto. Si se aplica a una serie de números x en 0, 1, ..., entonces x mod n será 0, 1, ..., n-1, 0, 1, ..., n-1, ad infinitum. Cuando su módulo n es una potencia de 2, entonces x mod n contará en binario de 0 a n-1, de nuevo a 0, a n-1, etc .; para el módulo n que se parece al binario 01xxxxx, x mod n recorrerá cada uno de esos bits de bajo orden xxxxx.
2. binario 1011000111011010 mod 1 es 0 (mod 2^0 produce los últimos bits cero, todo mod 1 es cero). binario 1011000111011010 mod binario 10000 es 1010 (mod 2^4 da los últimos cuatro bits).
3. La división y el resto del número binario por potencias de dos es particularmente eficiente porque solo está cambiando y enmascarando; matemáticamente no es nada especial.
4. Ejemplo: Véase la respuesta a la pregunta 2.