Dado un número entero, ¿cómo puedo encontrar la siguiente potencia más grande de dos utilizando twiddling?

Si tengo un número entero n , ¿cómo puedo encontrar el siguiente número k > n tal que k = 2^i , con algún elemento i de N por cambio de bit o lógica?

Ejemplo: Si tengo n = 123 , ¿cómo puedo encontrar k = 128 , que es una potencia de dos, y no 124 que solo es divisible por dos? Esto debería ser simple, pero se me escapa.

Para enteros de 32 bits, esta es una ruta simple y directa:

 unsigned int n; n--; n |= n >> 1; // Divide by 2^k for consecutive doublings of k up to 32, n |= n >> 2; // and then or the results. n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; // The result is a number of 1 bits equal to the number // of bits in the original number, plus 1. That's the // next highest power of 2. 

Aquí hay un ejemplo más concreto. Tomemos el número 221, que es 11011101 en binario:

 n--; // 1101 1101 --> 1101 1100 n |= n >> 1; // 1101 1100 | 0110 1110 = 1111 1110 n |= n >> 2; // 1111 1110 | 0011 1111 = 1111 1111 n |= n >> 4; // ... n |= n >> 8; n |= n >> 16; // 1111 1111 | 1111 1111 = 1111 1111 n++; // 1111 1111 --> 1 0000 0000 

Hay un bit en la novena posición, que representa 2 ^ 8, o 256, que de hecho es la siguiente potencia más grande de 2 . Cada uno de los turnos se superpone a todos los 1 bits existentes en el número con algunos de los ceros previamente intactos, produciendo eventualmente un número de 1 bit igual al número de bits en el número original. Agregar uno a ese valor produce una nueva potencia de 2.

Otro ejemplo; usaremos 131, que es 10000011 en binario:

 n--; // 1000 0011 --> 1000 0010 n |= n >> 1; // 1000 0010 | 0100 0001 = 1100 0011 n |= n >> 2; // 1100 0011 | 0011 0000 = 1111 0011 n |= n >> 4; // 1111 0011 | 0000 1111 = 1111 1111 n |= n >> 8; // ... (At this point all bits are 1, so further bitwise-or n |= n >> 16; // operations produce no effect.) n++; // 1111 1111 --> 1 0000 0000 

Y de hecho, 256 es la siguiente potencia más alta de 2 de 131.

Si el número de bits utilizados para representar el número entero es en sí mismo una potencia de 2, puede continuar ampliando esta técnica de manera eficiente e indefinida (por ejemplo, agregue una n >> 32 línea para enteros de 64 bits).

En realidad, hay una solución de ensamblaje para esto (desde el conjunto de instrucciones 80386).

Puede usar la instrucción BSR (Bit Scan Reverse) para buscar el bit más significativo en su número entero.

bsr escanea los bits, comenzando en el bit más significativo, en el operando de doble palabra o en la segunda palabra. Si los bits son todos cero, ZF se borra. De lo contrario, se configura ZF y se carga el índice de bit del primer bit establecido, mientras se explora en la dirección inversa, en el registro de destino

(Extraído de: http://dlc.sun.com/pdf/802-1948/802-1948.pdf )

Y que inc el resultado con 1.

asi que:

 bsr ecx, eax //eax = number jz @zero mov eax, 2 // result set the second bit (instead of a inc ecx) shl eax, ecx // and move it ecx times to the left ret // result is in eax @zero: xor eax, eax ret 

En las CPU más nuevas puede usar la instrucción lzcnt mucho más lzcnt (también conocida como rep bsr ). lzcnt hace su trabajo en un solo ciclo.

Una forma más matemática, sin bucles:

 public static int ByLogs(int n) { double y = Math.Floor(Math.Log(n, 2)); return (int)Math.Pow(2, y + 1); } 

Aquí hay una respuesta lógica:

 function getK(int n) { int k = 1; while (k < n) k *= 2; return k; } 

Aquí está la respuesta de John Feminella implementada como un bucle para que pueda manejar los enteros largos de Python :

 def next_power_of_2(n): """ Return next power of 2 greater than or equal to n """ n -= 1 # greater than OR EQUAL TO n shift = 1 while (n+1) & n: # n+1 is not a power of 2 yet n |= n >> shift shift < <= 1 return n + 1 

También regresa más rápido si n ya es una potencia de 2.

Para Python> 2.7, esto es más simple y más rápido para la mayoría de N:

 def next_power_of_2(n): """ Return next power of 2 greater than or equal to n """ return 2**(n-1).bit_length() 

enter image description here

Aquí hay uno salvaje que no tiene bucles, pero usa un flotador intermedio.

 // compute k = nextpowerof2(n) if (n > 1) { float f = (float) n; unsigned int const t = 1U < < ((*(unsigned int *)&f >> 23) - 0x7f); k = t < < (t < n); } else k = 1; 

Esto, y muchos otros hackeos, incluido el enviado por John Feminella, se pueden encontrar aquí .

supongamos que x no es negativo.

 int pot = Integer.highestOneBit(x); if (pot != x) { pot *= 2; } 

Si usa GCC, MinGW o Clang:

 template  T nextPow2(T in) { return (in & (T)(in - 1)) ? (1U < < (sizeof(T) * 8 - __builtin_clz(in))) : in; } 

Si usa Microsoft Visual C ++, use la función _BitScanForward() para reemplazar __builtin_clz() .

 function Pow2Thing(int n) { x = 1; while (n>0) { n/=2; x*=2; } return x; } 

Un poco de twiddling, dices?

 long int pow_2_ceil(long int t) { if (t == 0) return 1; if (t != (t & -t)) { do { t -= t & -t; } while (t != (t & -t)); t < <= 1; } return t; } 

Cada bucle separa directamente el bit menos significativo de 1 bit. NB Esto solo funciona cuando los números firmados están codificados en complemento a dos.

Mayor que / Mayor que o igual a

Los siguientes fragmentos son para el siguiente número k> n tal que k = 2 ^ i
(n = 123 => k = 128, n = 128 => k = 256) según lo especificado por OP.

Si desea la potencia más pequeña de 2 mayor que O igual a n , simplemente reemplace __builtin_clzll(n) por __builtin_clzll(n-1) dentro de los fragmentos de arriba.

C ++ 11 usando GCC o Clang (64 bits)

 constexpr uint64_t nextPowerOfTwo64 (uint64_t n) { return 1ULL < < (sizeof(uint64_t) * 8 - __builtin_clzll(n)); } 

Mejora con CHAR_BIT según lo propuesto por martinec

 #include  constexpr uint64_t nextPowerOfTwo64 (uint64_t n) { return 1ULL < < (sizeof(uint64_t) * CHAR_BIT - __builtin_clzll(n)); } 

C ++ 17 utilizando GCC o Clang (de 8 a 128 bits)

 #include  template  constexpr T nextPowerOfTwo64 (T n) { T clz = 0; if constexpr (sizeof(T) < = 32) clz = __builtin_clzl(n); // unsigned long else if (sizeof(T) <= 64) clz = __builtin_clzll(n); // unsigned long long else { // See https://stackoverflow.com/a/40528716 uint64_t hi = n >> 64; uint64_t lo = (hi == 0) ? n : -1ULL; clz = _lzcnt_u64(hi) + _lzcnt_u64(lo); } return T{1} < < (CHAR_BIT * sizeof(T) - clz); } 

Otros comstackdores

Si usa un comstackdor que no sea GCC o Clang, visite la página de Wikipedia que enumera las funciones bit a bit Count Count Zeroes :

  • Visual C ++ 2005 => Reemplazar __builtin_clzl() por _BitScanForward()
  • Visual C ++ 2008 => Reemplazar __builtin_clzl() por __lzcnt()
  • icc => Reemplazar __builtin_clzl() por _bit_scan_forward
  • GHC (Haskell) => Reemplazar __builtin_clzl() por countLeadingZeros()

Contribución bienvenida

Proponga mejoras en los comentarios. También proponga una alternativa para el comstackdor que usa, o su lenguaje de progtwigción ...

Ver también respuestas similares

  • la respuesta de nulleight
  • respuesta de ydroneaud

¿Qué tal algo así?

 int pot = 1; for (int i = 0; i < 31; i++, pot <<= 1) if (pot >= x) break; 

Solo necesitas encontrar el bit más significativo y cambiarlo una vez. Aquí hay una implementación de Python. Creo que x86 tiene una instrucción para obtener el MSB, pero aquí lo estoy implementando todo en Python directo. Una vez que tienes el MSB es fácil.

 >>> def msb(n): ... result = -1 ... index = 0 ... while n: ... bit = 1 < < index ... if bit & n: ... result = index ... n &= ~bit ... index += 1 ... return result ... >>> def next_pow(n): ... return 1 < < (msb(n) + 1) ... >>> next_pow(1) 2 >>> next_pow(2) 4 >>> next_pow(3) 4 >>> next_pow(4) 8 >>> next_pow(123) 128 >>> next_pow(222) 256 >>> 

¡Olvidalo! ¡Utiliza loop!

  unsigned int nextPowerOf2 ( unsigned int u) { unsigned int v = 0x80000000; // supposed 32-bit unsigned int if (u < v) { while (v > u) v = v >> 1; } return (v < < 1); // return 0 if number is too big } 
 private static int nextHighestPower(int number){ if((number & number-1)==0){ return number; } else{ int count=0; while(number!=0){ number=number>>1; count++; } return 1<  
 // n is the number int min = (n&-n); int nextPowerOfTwo = n+min; 
 #define nextPowerOf2(x, n) (x + (n-1)) & ~(n-1) 

o incluso

 #define nextPowerOf2(x, n) x + (x & (n-1))