5

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?

Skylion
  • 2,696
  • 26
  • 50
  • 5
    Look at its binary representation. A combination of mod and integer division will probably work. – Hovercraft Full Of Eels Sep 09 '13 at 00:45
  • Some of the C solutions here may be applicable: http://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2?rq=1 – Thilo Sep 09 '13 at 00:46
  • 1
    I'm trying to remember -- something like anding with 1 + the 1's complement. Anyway, I'm pretty sure it can be done in 4-5 simple operations. – Hot Licks Sep 09 '13 at 00:46
  • @Thilo - You simply linked back to this question. – Hot Licks Sep 09 '13 at 00:48
  • 2
    @Skylion, you should move the accepted answer back to Mitch (ask him to copy my illustrations in); I am only illustrating his answer – Bruce Martin Sep 09 '13 at 08:51
  • @Thilo What's most efficient in C may not be most efficient in Java. Languages are _not_ created equal. – arkon Aug 15 '14 at 22:54

3 Answers3

13

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.

Mitch Wheat
  • 295,962
  • 43
  • 465
  • 541
  • @MitchWheat The bottom one is not idiomatic. The compiler will throw an error because it will assume you want to assign an `int` to `f`. It should look like this `f = v != 0 && (v & (v - 1)) == 0;` – arkon Aug 15 '14 at 23:34
3

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

  1. Write the number in binary; you will see that a power of 2 has only a single one in it
  2. Fiddle with the various operators / boolean at boolean level and see what works

doing this, I found the following also work:

  A & (-A) == A        
 (not A) | (not A + 1) == -1    /* boolean not of a & (a-1) == 0 */
Bruce Martin
  • 10,358
  • 1
  • 27
  • 38
-1

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.

Dawood ibn Kareem
  • 77,785
  • 15
  • 98
  • 110