Fast way to find exponent of nearest superior power of 2

If I have a number a, I want the value of x in b=2^x, where b is the next power of 2 greater than a.

In case you missed the tag, this is Java, and a is an int. I'm looking for the fastest way to do this. My solution thusfar is to use bit-twiddling to get b开发者_StackOverflow, then do (int)(log(b)/log(2)), but I feel like there has to be a faster method that doesn't involve dividing two floating-point numbers.

What about a == 0 ? 0 : 32 - Integer.numberOfLeadingZeros(a - 1)? That avoids floating point entirely. If you know a is never 0, you can leave off the first part.

If anyone is looking for some "bit-twiddling" code that Andy mentions, that could look something like this: (if people have better ways, you should share!)

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

Not necessarily faster, but one liner:

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

If you need an answer that works for integers or floating point, both of these should work:

I would think that Math.floor(Math.log(a) * 1.4426950408889634073599246810019) + 1 would be your best bet if you don't want to do bit twiddling.

If you do want to bit-twiddle, you can use Double.doubleToLongBits(a) and then just extract the exponent. I'm thinking ((Double.doubleRawToLongBits(a) >>> 52) & 0x7ff) - 1022 should do the trick.

just do the following:

extract the highest bit by using this method (modified from 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;
}

combining both functions into this function to get a number 'b', that is the next power of 2 of a given number '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;
}

kind regards, dave

How about divide-and-conquer? As in:

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

Assuming a is unsigned, the divides should just be bit-shifts.

A binary IF-tree with 32 leaves should be even faster, getting the answer in 5 comparisons. Something like:

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.

Java provides a function that rounds down to the nearest power of 2. Thus a!=Integer.highestOneBit(a)?2*Integer.highestOneBit(a):a is a slightly prettier solution, assuming a is positive.

Storing Integer.highestOneBit(a) in a variable may further improve performance and readability.

To add to Jeremiah Willcock's answer, if you want the value of the power of 2 itself, then you will want:

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

Here is my code for the same. Will this be faster?

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