Check the Number of Powers of 2

Question

I have a number X , I want to check the number of powers of 2 it have ? For Ex

N=7  ans is 2 , 2*2
N=20 ans is 4, 2*2*2*2

Similar I want to check the next power of 2

For Ex:
N=14 Ans=16

Is there any Bit Hack for this without using for loops ? Like we are having a one line solution to check if it's a power of 2 X&(X-1)==0,similarly like that ?

http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer — Alexey Guseynov, Sep 19 '16 at 10:04
@AlexeyGuseynov i guess number of set bit does not give me the correct answer — user6250837, Sep 19 '16 at 10:10
So basically the first quetsion is about getting the int part of the log base 2 of N. The second question already have tons of duplicates here http://stackoverflow.com/q/466204/995714 http://stackoverflow.com/q/671815/995714 http://stackoverflow.com/q/3272424/995714 — phuclv, Sep 19 '16 at 10:30

score 2 · Answer 1 · answered Sep 19 '16 at 10:19

GCC has a built-in instruction called __builtin_clz() that returns the number of leading zeros in an integer. So for example, assuming a 32-bit int, the expression p = 32 - __builtin_clz(n) will tell you how many bits are needed to store the integer n, and 1 << p will give you the next highest power of 2 (provided p<32, of course).

There are also equivalent functions that work with long and long long integers.

Alternatively, math.h defines a function called frexp() that returns the base-2 exponent of a double-precision number. This is likely to be less efficient because your integer will have to be converted to a double-precision value before it is passed to this function.

score 0 · Answer 2 · edited May 23 '17 at 12:19

A number is power of two if it has only single '1' in its binary value. For example, 2 = 00000010, 4 = 00000100, 8 = 00001000 and so on. So you can check it using counting the no. of 1's in its bit value. If count is 1 then the number is power of 2 and vice versa.

You can take help from here and here to avoid for loops for counting set bits.

If count is not 1 (means that Value is not power of 2) then take position of its first set bit from MSB and the next power of 2 value to this number is the value having only set bit at position + 1. For example, number 3 = 00000011. Its first set bit from MSB is 2nd bit. Therefore the next power of 2 number is a value having only set bit at 3rd position. i.e. 00000100 = 4.

Check the Number of Powers of 2

2 Answers2