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

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

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

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

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

Ответы [ 17 ]

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

Для 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-битных целых чисел).

29 голосов
/ 26 августа 2009

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

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

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 выполняет свою работу за один цикл.

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

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

public static int ByLogs(int n)
{
    double y = Math.Floor(Math.Log(n, 2));

    return (int)Math.Pow(2, y + 1);
}
12 голосов
/ 24 августа 2009

Вот логичный ответ: 

function getK(int n)
{
  int k = 1;
  while (k < n)
    k *= 2;
  return k;
}
8 голосов
/ 03 октября 2013

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

enter image description here

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

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

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

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

3 голосов
/ 09 апреля 2017

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

Следующие фрагменты предназначены для следующего числа 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, как предложено martinec 

#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://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, посетите страницу Википедии, в которой перечислены Подсчет ведущих нулей побитовых функций :

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

Вклад приветствуется

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

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

2 голосов
/ 01 февраля 2012

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

int pot = Integer.highestOneBit(x);
if (pot != x) {
    pot *= 2;
}
2 голосов
/ 09 октября 2016

Если вы используете 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().

1 голос
/ 06 января 2015

Битвашка, говоришь? 

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-бит. Нотабене Это работает только тогда, когда числа со знаком кодируются в дополнение к двум.

Страница:
...