¿No puedes entender lo que está haciendo este progtwig de C?

Cuando me estaba preparando para una entrevista obtuve lo siguiente

count=0; for(i=1;i<=n;i++) { i=(i)&(i-1); //line 4 count++; } return count; //-------- i=21,22 same count. For what other values of i we get same count? 

No pude entender lo que está haciendo la línea 4. ¿Alguien puede ayudarme y darme la salida del progtwig?

Encontró la pregunta anterior (9) en el enlace http://placement.freshersworld.com/placement-papers/Mentor-Graphics/Placement-Paper-Aptitude-General-32412

Advertencia
Después de revisar su código por segunda vez, debo decir que puede comstackrse bien, pero usted va a encontrar un punto muerto, creo:

 for (i=1;i<=n;++i) { i = (i)&(i-1); cont++; } 

¿Lo que sucederá? Cuando i es 1 :

 i = 1&0;//is what line 4 boils down to 

Entonces, seré 0 , si el bucle comenzó, entonces n será al menos 1, por lo que la condición del bucle aún es verdadera:

 i<=n => 0 <= n ==> true 

Así que i se incrementa en 1 ( i++ ), y todo vuelve a empezar. La línea cuatro, una vez más, evalúa a:

 i = 1&0;//assigns 0 again to i 

Y estás de vuelta a la plaza uno. Este progtwig nunca terminará, simplemente repetirá la misma operación una y otra vez ...


Bueno, & es el operador bit a bit. Cuando se usa, como en su fragmento con 2 enteros, devuelve los bits que están "encendidos" o establecidos en 1 en ambos números. En un lenguaje sencillo: la expresión se evalúa como un nuevo conjunto de bits, que se establecieron en ambos operandos. Tomemos, por ejemplo, cuando i es 2:

 00000010 //2 00000001 // i - 1 -------- 00000000 

En este caso, ninguno de los bits se establece en 1 en ambos casos. Como de hecho este será el hecho para todos los poderes de dos, porque los poderes de 2 se ven así en binario:

 00000010 00000100 00001000 

Y una potencia de 2 menos 1 se ve así:

 00001000//power of 2 00000111 

En todos los demás casos, habrá al menos 1 bit que se establece en 1 en ambos casos:

 00000110 00000101 -------- 00000100 

Fácil.


Para obtener una descripción más completa y una explicación detallada de los operadores bitwise en C, siempre puede consultar la wiki sobre operadores bitwise en C

i & (i-1) devuelve 0 si i es una potencia de 2 o si i es 0, de lo contrario no será cero.

En la inspección, se establecerá en cero, el recuento se incrementará, luego volveré a ser 1, luego 0, y así sucesivamente.

No estoy seguro de que este bucle terminará.

La línea

 i = i & (i-1) 

borra el bit de conjunto más bajo de i . Así que un bucle como

 while (i) { i = i & (i-1); count++; } 

cuenta el número de bits establecidos en i . Tenga en cuenta que esto realmente solo funciona si i un tipo sin firmar. Si i es firmado y negativo, causa un comportamiento indefinido.

Es probable que el enlace que proporcione sea una pregunta que no recuerda (que quedó fuera del while (i) ) y que pregunta sobre un bucle como este.

El comentario “i = 21,22 mismo conteo” es una sugerencia de que 21 (10101) y 22 (10110) tienen el mismo número de bits establecidos.

Debo admitir que cuando leí su pregunta la primera vez, vi el ciclo while(i) como las líneas i=(i)&(i-1); count++; i=(i)&(i-1); count++; realmente solo tiene sentido en ese contexto, y es un lenguaje tan común de “pregunta trampa”.

& es un operador Y a nivel de bits. Se calcula de la siguiente manera:

por ejemplo: i = 8

 i & (i-1) is (1000) AND (0111) results 0000. 

Si ejecutas el progtwig, entra en un bucle infinito desde

 i=1 and (i) & (i-1) gives 0 

cada vez que me convierto en 1

Entonces, modifique el código de la siguiente manera y espero que obtenga la respuesta:

 for(i=1;i<=n;i++) { count=(i)&(i-1); printf(" i= %d count= %d",i,count); } 

El resultado es el siguiente:

 i= 1 count= 0 i= 2 count= 0 i= 3 count= 2 i= 4 count= 0 i= 5 count= 4 i= 6 count= 4 i= 7 count= 6 i= 8 count= 0 i= 9 count= 8 i= 10 count= 8 i= 11 count= 10 i= 12 count= 8 i= 13 count= 12 i= 14 count= 12 i= 15 count= 14 i= 16 count= 0 i= 17 count= 16 i= 18 count= 16 i= 19 count= 18 i= 20 count= 16 i= 21 count= 20 i= 22 count= 20 i= 23 count= 22 i= 24 count= 16 i= 25 count= 24