Учитывая целое число, как я могу найти следующую наибольшую степень двух, используя битовое перемешивание? - PullRequest
Новая
       52

Учитывая целое число, как я могу найти следующую наибольшую степень двух, используя битовое перемешивание?

72 голосов
/ 24 августа 2009

Если у меня есть целое число n, как я могу найти следующее число k > n такое, что k = 2^i, с некоторым i элементом N путем побитового сдвига или логики.

Пример: если у меня есть n = 123, как я могу найти k = 128, который является степенью двойки, а не 124, который делится только на два. Это должно быть просто, но это ускользает от меня.

Ответы [ 17 ]

1 голос
/ 24 августа 2009 
function Pow2Thing(int n)
{
    x = 1;
    while (n>0)
    {
        n/=2;
        x*=2;
    }
    return x;
}
0 голосов
/ 17 ноября 2010 
// n is the number
int min = (n&-n);
int nextPowerOfTwo = n+min;
0 голосов
/ 25 октября 2015 
#define nextPowerOf2(x, n) (x + (n-1)) & ~(n-1)

или даже 

#define nextPowerOf2(x, n)  x + (x & (n-1))
0 голосов
/ 31 июля 2015 
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;
    }
}
0 голосов
/ 12 января 2014

Забудь об этом! Он использует цикл! 

     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
     }
0 голосов
/ 24 августа 2009

Что-то вроде этого: 

int pot = 1;
for (int i = 0; i < 31; i++, pot <<= 1)
    if (pot >= x)
        break;
0 голосов
/ 25 августа 2009

Вам просто нужно найти самый значащий бит и сдвинуть его влево один раз. Вот реализация Python. Я думаю, что у x86 есть инструкция, чтобы получить MSB, но здесь я реализую все это прямо на Python. Если у вас есть MSB, это легко. 

>>> 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
>>>
Страница:
...