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".
- 2n = decimal = binary
- 20 = 1 = 1
- 21 = 2 = 10
- 22 = 4 = 100
- 23 = 8 = 1000
- 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).
- 2n -1 = decimal = binary
- 20 -1 = 0 = 0
- 21 -1 = 1 = 1
- 22 -1 = 3 = 11
- 23 -1 = 7 = 111
The binary operand '&' in C like languages is a logical 'and' which follows the truth table:
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')
00000 = 0
For some other number, (lets say 13), the equation would result in:
(13 & 12) == 0
(1101 & 1100) == 0
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
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 (loge), though any will do - just don't mix up log10 with loge.
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').
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
int main(int argc, char *argv)
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.