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

If I have a number that I am 开发者_JS百科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

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.

You could use the log function in cmath...

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

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

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.

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.

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

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
}