CODEWITHSUNDEEP
javaperformancemathrecursionbinary
Skylion
Skylion

Reputation: 2752

What is the most programatically efficient way to determine if a number is a power of 2?

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

Answers (3)

Mitch Wheat
Mitch Wheat

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

Bruce Martin
Bruce Martin

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

  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 */

Upvotes: 3

Dawood ibn Kareem
Dawood ibn Kareem

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

Related Questions