Быстрый способ найти показатель ближайшей превосходящей мощности 2

Если у меня есть число a, я хочу значение x в b = 2 ^ x, где b - следующая мощность 2 больше, чем a.

Если вы пропустили тег, это Java, а a - int. Я ищу самый быстрый способ сделать это. Мое решение таким образом состоит в том, чтобы использовать бит-twiddling для получения b, а затем do (int) (log (b)/log (2)), но я чувствую, что должен быть более быстрый метод, который не включает разделение двух плавающих символов, номера точек.

Ответы

Ответ 1

Как насчет a == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(a - 1)? Это полностью исключает плавающие точки. Если вы знаете, что a никогда не 0, вы можете оставить первую часть.

Ответ 2

Если кто-то ищет какой-то "бит-крутой" код, который упоминает Энди, это может выглядеть примерно так: (если у людей есть лучшие способы, вы должны поделиться!)

    public static int nextPowerOf2(final int a)
    {
        int b = 1;
        while (b < a)
        {
            b = b << 1;
        }
        return b;
    }

Ответ 3

Не обязательно быстрее, но один лайнер:

int nextPowerOf2(int num)
{
    return num == 1 ? 1 : Integer.highestOneBit(num - 1) * 2;
}

Ответ 4

просто выполните следующие действия:

извлечь самый старший бит с помощью этого метода (измененный с hdcode):

int msb(int x) {
   if (pow2(x)) return x;
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >> 16);
   x = x | (x >> 24);
   return x - (x >> 1);
}

int pow2(int n) {
   return (n) & (n-1) == 0;
}

объединение обеих функций в эту функцию для получения числа "b", то есть следующей степени 2 заданного числа "a":

int log2(int x) {
    int pow = 0;
    if(x >= (1 << 16)) { x >>= 16; pow +=  16;}
    if(x >= (1 << 8 )) { x >>=  8; pow +=   8;}
    if(x >= (1 << 4 )) { x >>=  4; pow +=   4;}
    if(x >= (1 << 2 )) { x >>=  2; pow +=   2;}
    if(x >= (1 << 1 )) { x >>=  1; pow +=   1;}
    return pow;
}

С уважением, Дэйв

Ответ 5

Если вам нужен ответ, который работает для целых чисел или с плавающей точкой, оба они должны работать:

Я бы подумал, что Math.floor(Math.log(a) * 1.4426950408889634073599246810019) + 1 будет вашим лучшим выбором, если вы не захотите делать бит-скрининг.

Если вы хотите использовать бит-twiddle, вы можете использовать Double.doubleToLongBits(a), а затем просто извлечь экспоненту. Я думаю, что ((Double.doubleRawToLongBits(a) >>> 52) & 0x7ff) - 1022 должен сделать трюк.

Ответ 6

Как насчет деления и покорения? Как в:

b = 0;
if (a >= 65536){a /= 65536; b += 16;}
if (a >= 256){a /= 256; b += 8;}
if (a >= 16){a /= 16; b += 4;}
if (a >= 4){a /= 4; b += 2;}
if (a >= 2){a /= 2; b += 1;}

Предполагая, что a не имеет знака, деления должны быть просто бит-сдвигами.

Бинарное IF-дерево с 32 листьями должно быть еще быстрее, получив ответ в 5 сравнениях. Что-то вроде:

if (a >= (1<<0x10)){
  if (a >= (1<<0x18)){
    if (a >= (1<<0x1C)){
      if (a >= (1<<0x1E)){
        if (a >= (1<<0x1F)){
          b = 0x1F;
        } else {
          b = 0x1E;
        }
      } else {
        if (a >= (1<<0x1D)){
          b = 0x1D;
        } else {
          b = 0x1C;
        }
      }
   etc. etc.

Ответ 7

Чтобы добавить к Иеремии Уиллкоку ответ, если вы хотите значение самой силы 2, то вам нужно:

(int) Math.pow(2, (a == 0) ? 0 : 32 - Integer.numberOfLeadingZeros(numWorkers));

Ответ 8

Вот мой код для того же. Будет ли это быстрее?

 int a,b,x,y;
    Scanner inp = new Scanner(System.in);
    a = inp.nextInt();
    y = (int) (Math.log(a)/Math.log(2));
    x = y +1;
    System.out.println(x);