Fast way to find exponent of nearest superior power of 2

Question

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

As I said in the question, _a_ is an int. _x_ is strictly non-negative. — Andy Shulman, Mar 09 '11 at 07:36
@Andy: Where did you say it in the question? You said you have a *number* `a`. It could have been a `short`, a `long` or even be `BigInteger`. Can it be `Integer.MAX_VALUE`, in which case `x` can be 32, but no higher? — Jon Skeet, Mar 09 '11 at 07:37
"In case you missed the tag, this is Java, and a is an int." And yes, _x_ is from 0 to 32. — Andy Shulman, Mar 09 '11 at 07:41
I've assumed you mean "next power of 2 greater than *or equal to a*", and that *a* is unsigned, and that *a* is 32 bits. — Mike Dunlavey, Mar 09 '11 at 13:41
You're correct about greater than or equal to. Unfortunately, there is no `unsigned` modifier in Java. — Andy Shulman, Mar 09 '11 at 17:37
Possible duplicate of [Rounding up to nearest power of 2](http://stackoverflow.com/questions/466204/rounding-up-to-nearest-power-of-2) — phuclv, Mar 04 '17 at 15:23

score 42 · Accepted Answer · answered Mar 09 '11 at 07:25

42

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.

answered Mar 09 '11 at 07:25

Jeremiah Willcock

30,161
7
76
78

I know _a_ is nonzero, so I can just go with `32 - Integer.numberOfLeadingZeros(a - 1)`. This looks perfect. Never knew that method existed. Thank you! – Andy Shulman Mar 09 '11 at 07:35
How about for long? – David Williams Aug 30 '16 at 18:31
6

`32` -> `Integer.SIZE` – bobah Aug 20 '17 at 09:56
1

Note that `1 << (Integer.SIZE - Integer.numberOfLeadingZeros(x - 1))` gives 1 for negative values and 0 (if your array size is 1 rather than 0, you can multiply it by 2 to create a bigger array); for powers of 2 it returns the same power of 2, e.g. 8 --> 8 (which, strictly speaking, is not the "next superior" power of 2, but 2*\*N --> 2*\*N is what is usually needed). For Integer.MAX_VALUE=2147483647 it returns Integer.MIN_VALUE=-2147483648. – 18446744073709551615 Sep 04 '22 at 05:10
(Continuing my other comment) Integer shifts are tricky: only the 5 least-significant bits are used, the rest is ignored. `1<<33==1<<1025==1<<1==2`. For 0 and negative numbers, the code `Integer.SIZE - Integer.numberOfLeadingZeros(x - 1)` returns 32, binary 10_0000, and the 5 bits that are not ignored by `<<` are all zero – 18446744073709551615 Sep 04 '22 at 05:30

score 14 · Answer 2 · answered Aug 01 '12 at 21:22

14

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

answered Aug 01 '12 at 21:22

xbakesx

13,202
6
48
76

2

Downvote. Doesn't answer the question. The question is: "I want the value of x in b=2^x, where b is the next power of 2 greater than or equal to a." (See comment by OP for "greater than or equal to" part.) This answer produces b, not x. – jcsahnwaldt Reinstate Monica Feb 03 '18 at 18:54
@jona That's true, if you want x you can just count the number of iterations of the while loop and return that. I don't know what you'd name that method though :-) – xbakesx Feb 04 '18 at 12:36

Chipopo Lagoral · Answer 3 · 2017-10-10T10:36:37.040

9

Not necessarily faster, but one liner:

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

edited Oct 10 '17 at 10:36

answered Oct 10 '17 at 10:24

Chipopo Lagoral

107
1
4

1

Downvote. Doesn't answer the question. The question is: "I want the value of x in b=2^x, where b is the next power of 2 greater than or equal to a." (See comment by OP for "greater than or equal to" part.) This answer produces b, not x. – jcsahnwaldt Reinstate Monica Feb 03 '18 at 18:52

Gabe · Answer 4 · 2011-03-09T07:43:16.110

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.

score 1 · Answer 5 · answered Aug 03 '11 at 19:37

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

Downvote. Doesn't answer the question. The question is: "I want the value of x in b=2^x, where b is the next power of 2 greater than or equal to a." (See comment by OP for "greater than or equal to" part.) This answer produces b, not x. — jcsahnwaldt Reinstate Monica, Feb 03 '18 at 18:55

score 0 · Answer 6 · answered May 10 '18 at 15:41

0

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.

answered May 10 '18 at 15:41

Yehuda Rimon

31
6

storing same calculation in a variable if no changes to the arguments happen in between, is something the compiler does by default, no? – Phil May 10 '18 at 15:55
@Phil the compiler would need to know that the function has no side-effects. I personally would not bank on it. – rghome Jan 09 '19 at 11:36

Mike Dunlavey · Answer 7 · 2011-03-09T12:51:03.950

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.

score -1 · Answer 8 · answered Apr 13 '14 at 00:00

-1

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

answered Apr 13 '14 at 00:00

EyasSH

3,679
22
36

Maverick · Answer 9 · 2015-06-19T18:45:19.957

-1

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

edited Jun 19 '15 at 18:45

answered Jun 19 '15 at 18:21

Maverick

39
4

Fast way to find exponent of nearest superior power of 2

9 Answers9