Power of Two solution

This is the solution to problem 9 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

(b & (b-1)) == 0

Visit the counting 1 bits node for a good explanation of why this works.

Of course, if you're using floating numbers and stuff, you're in trouble. Unless you use logarithms and type:

int(log(b)/log(2)) == log(b)/log(2)

A classic computer science interview question (these are becoming less common as their solutions are memorized by all comp sci students) is:

Give a one-line C expression to test whether an unsigned int is a power of two.

The answer to this is:

(n & (n-1)) == 0

The solution to this is built on the nature of logical operations and a property of of powers of 2 in binary.

All powers of two in binary are of the form "10*" meaning "a one followed by zero or more zeros".

• 2ⁿ = decimal = binary
• 2⁰ = 1 = 1
• 2¹ = 2 = 10
• 2² = 4 = 100
• 2³ = 8 = 1000
• ...

Likewise, 2ⁿ - 1 is of the form "1+|0" meaning "a string of one or more ones, or a zero" (2^0 is an edge case requireing the 'or a zero' part).

• 2ⁿ -1 = decimal = binary
• 2⁰ -1 = 0 = 0
• 2¹ -1 = 1 = 1
• 2² -1 = 3 = 11
• 2³ -1 = 7 = 111
• ...

The binary operand '&' in C like languages is a logical 'and' which follows the truth table:

   1   0
 +-------
1| 1   0
0| 0   0

This reads as 'if both values are 1, the result is true. Otherwise, the result is false'.

For an arbitrary power of 2 (lets take 2^4 (16)), plugged into the expression at top, this results in

(16 & 15) == 0
(10000 & 01111) == 0

(at this point line up the values and see which ones 'match')

10000
01111
-----
00000 = 0

For some other number, (lets say 13), the equation would result in:

(13 & 12) == 0
(1101 & 1100) == 0

1101
1100
----
1100 != 0

It has been brought to my attention that for testing 0 this would fail (in that it would succeed saying that 0 was a power of two). The value '-1' in two's compliment is all '1's. This results in

00000  (0)
11111  (-1)
-----
00000 = 0

To account for this the classic correct answer needs to be changed to handle the 'n = 0' case:

(n & (n-1)) == 0 && n

(yes, I checked, '==' binds tighter than '&&')

---

In computing, the challenge is always to come up with an abstraction where the base does not have to be two. Non-integer powers a number are not part of the problem because any number to some power may result in any number (umm, yea, 3 is a power of two... 2^1.584963... is 3). Outside of powers of two and the inherent properties of binary within a computer it is necessary to use logarithms (these are not trees in a disco).

Is '3.375' an integer power of '1.5'? To do this, one takes the log of both numbers. Most often, this is the natural log (log_e), though any will do - just don't mix up log₁₀ with log_e.

Solve for x where a is the number being tested (in this case 3.375) and b is the number being raised to some power (in this case '1.5').

 x
b  = a

To do this, one uses the logarithmic identity

ln(b^x) = x ln(b)
  # substitute a for b^x
ln(a)   = x ln(b)
  # divide each side by ln(b)
ln(a)/ln(b) = x

The question is then "is x an integer?" If the answer is 'yes', then a (3.375) is an integer power of b (1.5). In C, this would be

int(log(a)/log(b)) == log(a)/log(b)

In this case, the answer is 'yes':

1.5 ^ 3 = 3.375

One should realize that the this test does not always work within programing languages because of the possibility of round off error. If the result came back as '2.99999' because it was not able to represent '3' exactly the test would fail even though the answer is correct. This error happens most often at rather large and small values.

An example of this occurs with 0.75 ^ 2550

#include 
#include 

int main(int argc, char *argv[])
{
    printf("%f\n",log(pow(0.75,2550))/log(0.75));
    return 0;
}

The result of this is '2549.999982' which is not an integer and thus would result in a false value, even though the value tested was a power of 0.75.