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

Для 32-битных целых чисел это простой и понятный маршрут:

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

Вот более конкретный пример. Возьмем номер 221, который является 11011101 в двоичном формате:

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

В девятой позиции есть один бит, который представляет 2 ^ 8 или 256, что на самом деле является следующей наибольшей мощностью 2 . Каждый из сдвигов перекрывает все существующие 1 биты в числе с некоторыми из ранее нетронутых нhive, в итоге создавая число 1 бит, равное количеству бит в исходном числе. Добавление одного к этому значению дает новую мощность 2.

Другой пример; мы будем использовать 131, который равен 10000011 в двоичном формате:

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

И действительно, 256 – следующая самая высокая сила 2 из 131.

Если количество битов, используемых для представления целого, само является степенью 2, вы можете продолжить эту технику эффективно и неопределенно (например, добавить строку n >> 32 для 64-битных целых чисел).

На самом деле существует решение для сборки (начиная с набора команд 80386).

Вы можете использовать инструкцию BSR (Bit Scan Reverse) для сканирования наиболее значимого бита в вашем целой части.

bsr сканирует биты, начиная с самого значащего бита, в операнде двойного слова или втором слове. Если бит равен нулю, ZF очищается. В противном случае ZF устанавливается, и бит-бит первого установленного бита, найденного при сканировании в обратном направлении, загружается в регистр назначения

(Извлечено из: http://dlc.sun.com/pdf/802-1948/802-1948.pdf )

А чем результат с 1.

так:

 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 

В новых процессорах вы можете использовать гораздо более lzcnt инструкцию lzcnt (aka rep bsr ). lzcnt выполняет свою работу за один цикл.

Более математический путь, без петель:

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

Вот логический ответ:

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

Вот ответ Джона Феменеллы, реализованный как цикл, поэтому он может обрабатывать длинные целые числа 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 

Он также возвращается быстрее, если n уже имеет мощность 2.

Для Python> 2.7 это проще и быстрее для большинства N:

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

Вот дикая, которая не имеет циклов, но использует промежуточное поплавок.

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

Это и многие другие хитроумные хаки, в том числе и представленные Джоном Феминеллой, можно найти здесь .

предположим, что х не является отрицательным.

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

Если вы используете GCC, MinGW или Clang:

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

Если вы используете Microsoft Visual C ++, используйте функцию _BitScanForward() для замены __builtin_clz() .

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

Вы говорите?

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

Каждый цикл разбивает наименее значимые 1 бит. NB Это работает только там, где подписанные числа закодированы в двух дополнениях.

Больше / Больше или равно

Следующие ниже fragmentы для следующего числа k> n такие, что k = 2 ^ i
(n = 123 => k = 128, n = 128 => k = 256), как указано OP.

Если вы хотите, чтобы наименьшая степень 2 больше OR, равная n, просто замените __builtin_clzll(n) на __builtin_clzll(n-1) пределах вышеприведенных fragmentов.

C ++ 11 с использованием GCC или Clang (64 бит)

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

Улучшение с использованием CHAR_BIT предложенное martinec

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

C ++ 17 с использованием GCC или Clang (от 8 до 128 бит)

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

Другие компиляторы

Если вы используете компилятор, отличный от GCC или Clang, перейдите на страницу Википедии, в которой перечислены граничные функции Count Leading Zeroes :

• Visual C ++ 2005 => Заменить __builtin_clzl() на _BitScanForward()
• Visual C ++ 2008 => Заменить __builtin_clzl() на __lzcnt()
• icc => Заменить __builtin_clzl() на _bit_scan_forward
• GHC (Haskell) => Заменить __builtin_clzl() по countLeadingZeros()

Вступление приветствуется

Предложите улучшения в комментариях. Также предлагайте альтернативу используемому компилятору или вашему языку программирования ...

См. Также похожие ответы

• ответ nulleight
• ответ ydroneaud

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

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

Вам просто нужно найти самый значительный бит и сдвинуть его один раз. Вот реализация 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 >>> 

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

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