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
^{n} = decimal = binary
- 2
^{0} = 1 = 1
- 2
^{1} = 2 = 10
- 2
^{2} = 4 = 100
- 2
^{3} = 8 = 1000
- ...

Likewise, 2

^{n} - 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
^{n} -1 = decimal = binary
- 2
^{0} -1 = 0 = 0
- 2
^{1} -1 = 1 = 1
- 2
^{2} -1 = 3 = 11
- 2
^{3} -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_{10} 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.