Determining if an integer is a power of 2

Ever wondered how to find if an integer is a power of 2 in a single statement,

this is a piece of code 4 u...

unsigned int v; // we want to see if v is a power of 2

bool f; // the result goes here

f = (v & (v - 1)) == 0;

Note that 0 is incorrectly considered a power of 2 here. To remedy this, use:

f = !(v & (v - 1)) && v;

This is how it works...

Case 1: Let v = 10 ,v - 1 = 9

Lets test v & (v-1)==0

v = 1010, v = 1001

1010 (v)

& 1001 (v-1)

------

1000 v & (v-1)(8 in decimal form)

------

v & (v -1) == 0 -> 8 (which is treated as true)== 0(false)

Hence, false is returned and 10 not a power of two.

Considering the alternative

!(v & (v - 1)) && v

!(8) && 10 -> 0 && 1 -> 0(Remember, any number greater than 0 in C is considered

as true and its negation is false i.e. 0 as '!' is

a logical operator.)

Case 2: Let v = 8 ,v - 1 = 7

Lets consider v & (v-1)==0

v = 1000, v = 0111

1000 (v)

& 0111 (v-1)

------

0000 v & (v-1)(0 in decimal form)

------

v & (v -1) == 0 gives 0 == 0 Returns true

Hence 8 is a power of two.

Considering the alternative

!(v & (v - 1)) && v

!(0) && 8 -> 1(true) && 1 (true)-> 1(true)(Remember, any number greater than 0 in C considered as true and its negation is false i.e. 0 as '!' is a logical operator.)

Hence 8 is a power of 2.

## No comments:

Post a Comment