La siguiente función se afirma para evaluar si un número es una potencia entera de 4. ¿No entiendo muy bien cómo funciona?evaluar si un número es potencia entera de 4
bool fn(unsigned int x)
{
if (x == 0) return false;
if (x & (x - 1)) return false;
return x & 0x55555555;
}
La primera condición descarta 0, que obviamente no es una potencia de 4, pero pasaría incorrectamente las siguientes dos pruebas. (EDIT:.. No, no sería, como ha señalado la primera prueba es redundante)
El siguiente es un buen truco: Se devuelve verdadero si y sólo si el número es una potencia de 2. Una potencia de dos se caracteriza por tener solo un bit establecido. Un número con un bit configurado menos uno da como resultado un número con todos los bits anteriores a ese bit que se está configurando (es decir, 0x1000 menos uno es 0x0111). Y esos dos números, y obtienes 0. En cualquier otro caso (es decir, no potencia de 2), habrá al menos un bit que se superpone.
Así que en este punto, sabemos que es una potencia de 2.
x & 0x55555555 vuelve distinto de cero (= true) si los hay incluso Bit fijó (el bit 0, bit 2, el bit 4, bit 6, etc.) Eso significa que tiene una potencia de 4. (es decir, 2 no pasa, pero 4 pasa, 8 no pasa, 16 pasa, etc.).
Cada poder de 4 debe estar en la forma de 1 seguido de un número par de ceros (representación binaria): 100 ... 00:
100 = 4
10000 = 16
1000000 = 64
La primera prueba ("si") es obvia.
Al restar 1 de un número de la forma XY100 ... 00 que presentamos lo XY011 ... 11. Entonces, la 2da prueba verifica si hay más de un "1" bit en el número (XY en este ejemplo).
La última prueba comprueba si este único "1" está en la posición correcta, es decir, bit # 2,4,6, etc. De lo contrario, el enmascaramiento (&) devolverá un resultado distinto de cero.
x & (x - 1) quita el 1 bit más bajo de un número. – starblue