@dtfinch said:
return (value&(value-1))==0; I think
Thanks, dtfinch, you have it right. The other attempts? Kind of... bizzare. At least the original code worked! NONE of the suggestions before yours did. In Scheme
(define (is-power-of-2 x) (= 0 (bitwise-and x (- x 1)))
(is-power-of-2 0) -> #t, 0, 1, 2 are powers of 2, 3 is not, 4 is, 5, 6, 7 are not, 8 is -- feel free to fill in the test cases
(is-power-of-2 6) -> #f
(is-power-of-2 8) -> #t
Note that this formulation works the same as the original.
Why it works:
A power of two represented in binary is 1 0*, that is, a single 1 followed by zero or more 0s.
Subtracting one from this number results in 0 1*, where the pattern 1* is a number of 1s that is the same as the number of zeros in the original number (0*).
"And"ing these gives 0 iff the original number followed the first pattern -- because a non power-of-2 number would have had at least a one bit somewhere else. This would have "stopped" the subtraction carry too early. For example, consider the 3 bit numbers (100 through 111):
x=100 x-1=011, & -> 0
x=110, x-1=101, & -> 100
x=101, x-1=100, & -> 100
x=111, x-1=110, & -> 110
Notice the only subtraction that carries from the highest bit is the power of 2, because that one is the only one that will propagate the carry that far.
Mind you, the original formulation was clear, and would execute in a time proportional to the number of bits in the argument. It also only used integer operations (which may be important if bitwise wasn't implemented for the particular integer implementation). It isn't bad, and I would have profiled before replacing it. The replacement ((n) & (n - 1)) == 0 requires a LOT more documentation (like this entire post).