What is the quickest way to test a nonzero value to see if it is a power of 2?

Assuming you''re talking about some form of integer value (as oppossed to floating point) only one bit should be active if it is 1, 2, or a power of 2.


http://druidgames.cjb.net/

Well, if you''re familiar with some basic high school math (depends how old you are I guess) there might be a log(...) function in math.h, in which case you can test if log(n)/log(2) is an integer.

Otherwise, you can run through a loop (or you could even use a recursive function) that divides the number by two until its value is 1, and if it falls below 1 without being equal to it, then it''s not a power of 2.

Here''s how to do it with recursion:

bool PowerOfTwo(float num)
{
if (num<1) return false;
else if (num>1) return PowerOfTwo(num/2);
else return true;
}

Here, the first means if the number is less than one, it''s obviously not a power of two (unless it''s a decimal power, which I won''t get into)

The second line says if it''s more than one, we''ll keep on going with a smaller number

And, of course, if the number is 1, we must have arrived at it from 2, which came from 4, etc.

Keep in mind that this function would have to take a float as its parameter, because dividing an integer such as 9 by 2 yields 4, and you''d end up with the impression that 9 is a power of 2

The simple test is to see if it has only one bit set.

bool IsPowerOf2(int value)
{
int bitcount = 0;
int index;

for (index = 0; index < 32; ++index)
{
if (value & 0x0001)
++bitcount;
value = value >> 1;
}

return(bitcount == 1);
}



Steve ''Sly'' Williams  Code Monkey  Krome Studios

Or you could just start at one and double it, testing against the value.

bool IsPowerOf2(int value)
{
int index = 1;

while (index < value)
index = index << 1;

return(index == value);
}

This would be faster than my previous solution since it will find the solution faster for lower numbers, whereas the previous solution would be the same time for all numbers.

Steve ''Sly'' Williams  Code Monkey  Krome Studios

Oh, and those ints should be unsigned. Negative numbers don''t count.

Steve ''Sly'' Williams  Code Monkey  Krome Studios

The easy trick, for an unsigned non-zero 2''s compliment integer is that n&(n-1)==0 iff n is a power of 2. To see why this works consider that if n is a power of 2 in it''s representation in binary will look like 100000. subtract 1 and you get 1''s where all the zeros were, and a zero for the single 1 in our original n. If there were more than one bit set in the original number then only the least significant bit, and those bits less than that will be changed by subtracting one. As there would be unchanged bits in n-1, the and would be non-zero.

Zero is a false positive, negitive numbers don''t work.