Учитывая целое число, как я могу найти следующую наибольшую степень двух, используя битовое перемешивание?
Если у меня есть целое число nкак найти следующий номер k > n такой, что k = 2^i, с некоторыми i элемент N с помощью побитового сдвига или логики.
Пример: если у меня есть n = 123как я могу найти k = 128, который является степенью двойки, а не 124 который делится только на два. Это должно быть просто, но это ускользает от меня.
17 ответов
Для 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.
Вот более конкретный пример. Давайте возьмем число 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
В девятой позиции есть один бит, который представляет 2^8 или 256, что на самом деле является следующей по величине степенью 2. Каждое из сдвигов перекрывает все существующие 1 бит в числе с некоторыми из ранее нетронутых нулей, в конечном итоге получая число 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
И действительно, 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 инструкция (иначе 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()
Больше или больше или равно
Следующие фрагменты предназначены для следующего числа k > n, такого что k = 2 ^ i
(n = 123 => k = 128, n = 128 => k = 256), как указано в OP.
Если вы хотите, чтобы наименьшая степень 2 была больше ИЛИ, равной n, просто замените __builtin_clzll(n) от __builtin_clzll(n-1) в приведенных выше фрагментах.
C++ 11 с использованием GCC или Clang (64 бита)
constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
return 1ULL << (sizeof(uint64_t) * 8 - __builtin_clzll(n));
}
Улучшение с помощью CHAR_BIT по предложению Мартинека
#include <cstdint>
constexpr uint64_t nextPowerOfTwo64 (uint64_t n)
{
return 1ULL << (sizeof(uint64_t) * CHAR_BIT - __builtin_clzll(n));
}
C++17 с использованием GCC или Clang (от 8 до 128 бит)
#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://stackru.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()
Вклад приветствуется
Пожалуйста, предложите улучшения в комментариях. Также предложите альтернативу для компилятора, который вы используете, или вашего языка программирования...
Смотрите также похожие ответы
Вот дикий, который не имеет петель, но использует промежуточное плавание.
// 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;
Этот и многие другие хитроумные хаки, в том числе добавленные Джоном Феминеллой, можно найти здесь.
Если вы используете GCC, MinGW или Clang:
template <typename T>
T nextPow2(T in)
{
return (in & (T)(in - 1)) ? (1U << (sizeof(T) * 8 - __builtin_clz(in))) : in;
}
Если вы используете Microsoft Visual C++, используйте функцию _BitScanForward() заменить __builtin_clz(),
Предположим, что х не является отрицательным.
int pot = Integer.highestOneBit(x);
if (pot != x) {
pot *= 2;
}
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. Это работает только тогда, когда числа со знаком кодируются в дополнение к двум.
Вам просто нужно найти самый значимый бит и сдвинуть его влево один раз. Вот реализация 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
}
Как насчет чего-то вроде этого:
int pot = 1;
for (int i = 0; i < 31; i++, pot <<= 1)
if (pot >= x)
break;
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;
}
}
#define nextPowerOf2(x, n) (x + (n-1)) & ~(n-1)
или даже
#define nextPowerOf2(x, n) x + (x & (n-1))
// n is the number
int min = (n&-n);
int nextPowerOfTwo = n+min;