Thursday, 7 June 2012

Find if number is a power of two, and returns it power


'a' is power of two iff:  (a & (a-1) == 0).

To calculate the highest power 'a',

  • iteratively shift the bits of a number to right
  • increment a counter each time you shift right
  • repeat above 2 steps until number > 0.
  • 'counter' gives the value if the highest power.
  • No. of loops = 32 ( width of the number)
Better solution:
To find more optimally one can make a lookup table, of say size 4, which stores the power of 2/(number of set bits) and then run the loop 32/4 = 8 times. 

Optimal Solution:
To optimize this even further we can use divide and conquer, at each step find the half of the 32 bit number which contains the set bit. And do this recursively. We need just 5 (= log 32) iterations in this method.

No comments:

Post a Comment