Reputation: 2752
Just a simple of boolean true/false that is very efficient would be nice. Should I use recursion, or is there some better way to determine it?
Upvotes: 5
Views: 987
Reputation: 300837
From here:
Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2 bool f; // the result goes here f = (v & (v - 1)) == 0;
Note that 0 is incorrectly considered a power of 2 here. To remedy this, use:
f = v && !(v & (v - 1));
Why does this work? An integer power of two only ever has a single bit set. Subtracting 1 has the effect of changing that bit to a zero and all the bits below it to one. AND
'ing that with the original number will always result in all zeros.
Upvotes: 13
Reputation: 10573
An Integer power of two will be a 1 followed by one or more zero's
i.e.
Value value -1 (binary)
10 2 1
100 4 11
1000 8 111
10000 16 1111
as mitch said
(value & (value-1)) == 0
when value is a power of 2 (but not for any other number apart from 1 / 0 and 1 is normally regarded as 2 raised to the power of zero).
For mitch's solution, where numbers > 0 that are not powers of 2 i.e.
value value - 1 V & (v-1)
1000001 1000000 1000000
1000010 1000001 1000000
1000100 1000011 1000000
1001000 1000111 1000000
1000011 1000010 1000010
1000101 1000100 1000100
1000111 1000110 1000110
and never zero.
Subtracting 1 from a number reverses the bits up unto and including the first 1; for power's of two's there is only one '1' so Value & (Value-1) == 0, for other numbers second and subsequent 1's are left un-affected.
Zero will need to be excluded
Another possible solution (probably slightly slower) is
A & (-A) == A
Powers of 2:
A -A
00001 & 11111 = 00001
00010 & 11110 = 00010
00100 & 11100 = 00100
Some other numbers:
A -A
00011 & 11101 = 00001
00101 & 11011 = 00001
Again you need to exclude 0 as well
To solve this problem, I did
doing this, I found the following also work:
A & (-A) == A
(not A) | (not A + 1) == -1 /* boolean not of a & (a-1) == 0 */
Upvotes: 3
Reputation: 79875
Not sure whether you mean efficient in terms of computation speed, or in terms of lines of code. But you could try value == Integer.highestOneBit(value)
. Don't forget to exclude zero if you need to.
Upvotes: -1