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

2 minutos de lectura

avatar de usuario
Vishwanath Dalvi

Posibles duplicados:

Consulta sobre cómo saber si el número es una potencia de 2
¿Qué hace esta función?

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

  • Consulte esta pregunta: stackoverflow.com/questions/3265942/what-does-this-function-do/…

    – Vladímir

    13 de enero de 2011 a las 9:12

  • @Paul R, para mí no es un duplicado (aunque relacionado), este viene del revés, se podría decir.

    – Peter Torök

    13 de enero de 2011 a las 9:25


  • Convierte el 1 más a la derecha en 0 del modo binario de n. Si el resultado es igual a 0, significa que solo hay un 1 en el modo binario de n, lo que significa que n es potencia de 2.

    – adiós

    12 de noviembre de 2019 a las 12:34

avatar de usuario
paxdiablo

es averiguar 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 te dará 111...111. Entonces, cuando tú Y esos juntos, obtienes cero, como con:

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

Cualquier valor de entrada que no sea potencia de dos (que no sea cero) no darte cero cuando realices esa operación.

Por ejemplo, probemos 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

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

  • ¿Cómo es que 7 y -1 tienen 0111?

    – sofs1

    16 de octubre de 2018 a las 3:59


  • n & (n-1) ayuda a identificar el valor del último bit. Dado que el bit menos significativo para n y n-1 son (0 y 1) o (1 y 0) . Consulte la tabla anterior. (n & (n-1)) == 0 solo comprueba si n es una potencia de 2 o 0.

    – sofs1

    16 de octubre de 2018 a las 7:57

  • es un problema de codigo lelet

    – Jerry An

    9 de febrero de 2021 a las 9:06

avatar de usuario
pablo r

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

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

avatar de usuario
Sarnold

Comprueba si n es una potencia de 2: ¿Qué hace el código bit a bit “$n & ($n – 1)”?

avatar de usuario
neil

Es una operación bit a bit entre un número y su número anterior. La única forma en que esta expresión podría ser falsa es si n es una potencia de 2, por lo que esencialmente estás verificando si no es una potencia de 2.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad