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

language-agnostic bit-manipulation

Question

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.

Answer 1

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 <cstdint>
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 <cstdint>
template <typename T>
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://.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 compiladores

Si usa un compilador que no sea GCC o Clang, visite la página de Wikipedia que enumera las en.wikipedia.org/wiki/Find_first_set#Tool_and_library_support :

• 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 compilador que usa, o su lenguaje de programación ...

Ver también respuestas similares

• la respuesta de nulleight
• respuesta de ydroneaud

Answer 2

¡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
}

Answer 3

¿Qué tal algo así?

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

Answer 4

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()

Answer 5

Aquí hay una respuesta lógica:

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

Answer 6

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 here .

Answer 7

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.

Answer 8

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).

Answer 9

Si usa GCC, MinGW o Clang:

template <typename T>
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() .

Answer 10

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
>>>

Answer 11

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.

Answer 12

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);
}

Answer 13

supongamos que x no es negativo.

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

Answer 14

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

o incluso

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

Answer 15

// n is the number
int min = (n&-n);
int nextPowerOfTwo = n+min;

Answer 16

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

Answer 17

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<<count;
}
}