Is there an easy way to get which power of two a number is?

Question

If I have a number that I am certain is a power of two, is there a way to get which power of two the number is? I have thought of this idea: Having a count and shifting the number right by 1 and incrementing the count until the number is 0. Is there another way, though? Without keeping a counter?

Edit: Here are some examples: 8 -> returns 3 16 -> returns 4 32 -> returns 5

complement your number, and then: possible duplicate of [Getting the number of trailing 1 bits](http://stackoverflow.com/questions/2380728/getting-the-number-of-trailing-1-bits) — Greg Hewgill, Jun 03 '11 at 03:43
Almost identical to: http://stackoverflow.com/questions/994593/how-to-do-an-integer-log2-in-c ; see also: http://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set and http://stackoverflow.com/questions/1478023/index-of-lowest-order-bit — Matty K, Jun 03 '11 at 03:56
See [here](http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious), it has fast methods for any bit-twiddling hacks you can imagine (lookup tables, etc.). — user541686, Jun 03 '11 at 03:44

score 2 · Answer 1 · edited May 23 '17 at 12:26

2

The most elegant method is De Bruijn sequences. Here's a previous answer I gave to a similar question on how to use them to solve the problem:

Bit twiddling: which bit is set?

An often-more-practical approach is using your cpu's built-in instruction for finding the first/last bit set.

edited May 23 '17 at 12:26

Community

1
1

answered Jun 03 '11 at 03:56

R.. GitHub STOP HELPING ICE

208,859
35
376
711

score 1 · Answer 2 · answered Jun 03 '11 at 03:43

1

You could use the log function in cmath...

double exponent = log(number)/log(2.0);

...and then cast it to an int afterwards.

answered Jun 03 '11 at 03:43

Pace

41,875
13
113
156

Not sure about floating precision, but this works on more than just powers of 2! – Nathan Goings Jan 23 '22 at 18:25

score 1 · Answer 3 · answered Jun 03 '11 at 03:44

1

If that number is called x, you can find it by computing log2f(x). The return value is a float.

You will need to include <math.h> in order to use log2f.

answered Jun 03 '11 at 03:44

loudandclear

2,306
1
17
21

score 1 · Answer 4 · answered Jun 03 '11 at 03:46

That method certainly would work. Another possible way would be to eliminate half of the possibilities every time. Say you have an 8 bit number: 00010000

Bitwise and your number where half of the bits are one, and the other half is zero, say 00001111.

00010000 & 00001111 = 00000000

Now you know it's not in the first four bits. Do this repeatedly, until you don't get 0:

00010000 & 00110000 = 00010000

And than narrow it down to one possible bit which is 1, which is your power of two.

score 0 · Answer 5 · answered Jun 03 '11 at 04:18

Use binary search instead of linear:

public void binarySearch() throws Exception {
  int num = 0x40000;

  int k = 0;
  int shift = 16; // half of the size of the type (for in 16, etc)
  int a = 0xffff; // lower half should be f's

  while (shift != 0) {
    if ((num & a) == 0) {
      num = num >>> shift;
      k += shift;
      shift >>= 1;
    } else {
      shift >>= 1;
    }
    a = a >>> shift;
  }
  System.out.println(k);
}

score 0 · Answer 6 · answered Jan 23 '22 at 18:47

0

If you're doing a for loop like I am, one method is to power the loop counter before comparison:

for (var i = 1; Math.pow(2, i) <= 1048576; i++) {
  // iterates every power of two until 2^20
}

answered Jan 23 '22 at 18:47

Nathan Goings

1,145
1
15
33

Is there an easy way to get which power of two a number is?

6 Answers6