Agradecería ayuda para explicar la siguiente operación de bits. Disculpe mi falta de comprensión de la aritmética de bits.

int max = ~0;   
int left = max - ((1 << j) - 1); 

¿Cuál será el resultado de esta operación? ¿Es (1<<(j-1)) equivalente a ((1 << j) - 1)?

2
IUnknown 2 mar. 2017 a las 19:23

2 respuestas

La mejor respuesta

(1 << j) - 1 es un número con j uno bits a la derecha

        j bits
       ┌──────┐
00...0011...111

max es un número con todos uno bits

11...1111...111

Cada bit de max se convertirá en 0 al restar del bit de (1 << j) - 1, y permanecerá 1 de lo contrario. Por lo tanto, max - ((1 << j) - 1) producirá un valor con j cero bits a la derecha

           j...210 ← bit position
    11...1111...11
 -  00...0011...11
──────────────────
    11...1100...00

Eso significa que el resultado es el bit a bit no de (1 << j) - 1, es decir

max - ((1 << j) - 1) == ~((1 << j) - 1)

¿Es (1 << (j-1)) equivalente a ((1 << j) - 1)?

1 << (j-1) desplaza 1 j-1 lugares a la izquierda y produce 2 j - 1 , por lo que tiene j-1 ceros a la derecha seguidos de uno {{X3} }. (1 << j) - 1 da un número con j ceros a la derecha que es 2 j - 1, como se dijo anteriormente. ¿Puedes adivinar que son similares o no?

0
phuclv 2 dic. 2019 a las 02:42

Sigue las siguientes fórmulas,

  • Caso 1

    (1 << j) - 1) is equal to 2^j-1 [j = 1,2...]
    
  • Caso: 2

    (1<<(j-1)) is equal to 2^(j-1) [j = 1,2,3...]
    

¿Es (1 << (j-1)) equivalente a ((1 << j) - 1)?

No , obviamente de las fórmulas anteriores.

¿Cuál será el resultado de esta operación?

Para esta pregunta, max será " -1 " [bitwise NOT (0) es equivalente al complemento de todos los valores de bit de 0]

Entonces la fórmula será

izquierda = - (2 j )

Si j = -1 o j = 0 , las fórmulas anteriores no funcionarán como se esperaba, porque 1<<-1 no está definido comportamiento en C. Más detalles en los enlaces siguientes.

https://stackoverflow.com/a/4945765/3979414

http://c0x.coding-guidelines.com/6.5.7.html

1
phuclv 9 dic. 2019 a las 13:33