n & (n-1) ¿Qué hace esta expresión?

Question

duplicados posibles:
Query about working out whether number is a power of 2
What does this function do?

n & (n-1) - Dónde se puede utilizar esta expresión?

Answer 1

Está averiguando si n es 0 o una potencia exacta de dos.

Funciona porque una potencia binaria de dos es de la forma 1000...000 y restando uno le dará 111...111. Entonces, cuando usted y los que en conjunto, se obtiene cero, como por ejemplo con:

1000 0000 0000 0000 
& 111 1111 1111 1111 
    ==== ==== ==== ==== 
= 0000 0000 0000 0000 

Cualquier valor de entrada no-poder-de-dos (distinta de cero) no dar a poner a cero al realizar esa operación .

Por ejemplo, vamos a probar todas las combinaciones de 4 bits:

 <----- binary ----> 
n  n n-1 n&(n-1) 
-- ---- ---- ------- 
0 0000 0111 0000 * 
1 0001 0000 0000 * 
2 0010 0001 0000 * 
3 0011 0010 0010 
4 0100 0011 0000 * 
5 0101 0100 0100 
6 0110 0101 0100 
7 0111 0110 0110 
8 1000 0111 0000 * 
9 1001 1000 1000 
10 1010 1001 1000 
11 1011 1010 1010 
12 1100 1011 1000 
13 1101 1100 1100 
14 1110 1101 1100 
15 1111 1110 1110 

Se puede ver que sólo 0 y las potencias de dos (1, 2, 4 y 8) dan como resultado un patrón 0000/false bits, todos los demás son distintos de cero o true.

Answer 2

Devuelve 0 si n es una potencia de 2 (NB: solo funciona para n > 0). Entonces puede probar para una potencia de 2 como esta:

bool isPowerOfTwo(int n) 
{ 
    return (n > 0) && ((n & (n - 1)) == 0); 
} 

Answer 3

Es una operación bit a bit entre un número y su número anterior. Única manera esta expresión pudiera ser falso es si n es una potencia de 2, por lo que en esencia lo que está verificando si no es una potencia de 2.

Answer 4

Se comprueba si n es una potencia de 2: What does the bitwise code "$n & ($n - 1)" do?