How to check if a number is a power of 2

Question

Today I needed a simple algorithm for checking if a number is a power of 2   The algorithm needs to be    Simple Correct for any ulong value    I came up with this simple algorithm   private bool IsPowerOfTwo ulong number        if  number    0          return false       for  ulong power   1  power  gt  0  power   power  lt  lt  1                   This for loop used shifting for powers of 2  meaning            that the value will become 0 after the last shift             from binary 1000   0000 to 0000   0000  then  the  for             loop will break out           if  power    number              return true          if  power  gt  number              return false            return false      But then I thought  how about checking if log2 x is an exactly round number  But when I checked for 2 63 1  Math Log returned exactly 63 because of rounding  So I checked if 2 to the power 63 is equal to the original number - and it is  because the calculation is done in doubles and not in exact numbers   private bool IsPowerOfTwo 2 ulong number        double log   Math Log number  2       double pow   Math Pow 2  Math Round log        return pow    number      This returned true for the given wrong value  9223372036854775809   Is there a better algorithm

User · Answer

The following addendum to the accepted answer may be useful for some people:

A power of two, when expressed in binary, will always look like 1 followed by n zeroes where n is greater than or equal to 0. Ex:

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

and so on.

When we subtract 1 from these kind of numbers, they become 0 followed by n ones and again n is same as above. Ex:

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

and so on.

Coming to the crux

What happens when we do a bitwise AND of a number x, which is a power of 2, and x - 1?

The one of x gets aligned with the zero of x - 1 and all the zeroes of x get aligned with ones of x - 1, causing the bitwise AND to result in 0. And that is how we have the single line answer mentioned above being right.

Further adding to the beauty of accepted answer above -

So, we have a property at our disposal now:

When we subtract 1 from any number, then in the binary representation the rightmost 1 will become 0 and all the zeroes to the left of that rightmost 1 will now become 1.

One awesome use of this property is in finding out - How many 1s are present in the binary representation of a given number? The short and sweet code to do that for a given integer x is:

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

Another aspect of numbers that can be proved from the concept explained above is "Can every positive number be represented as the sum of powers of 2?".

Yes, every positive number can be represented as the sum of powers of 2. For any number, take its binary representation. Ex: Take number 117.

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1

User · Answer

private static bool IsPowerOfTwo ulong x        var l   Math Log x  2       return  l    Math Floor l

User · Answer

Example  0000 0001    Yes 0001 0001    No   Algorithm   Using a bit mask  divide NUM the variable in binary IF R  gt  0 AND L  gt  0  Return FALSE Otherwise  NUM becomes the one that is non-zero IF NUM   1  Return TRUE Otherwise  go to Step 1   Complexity  Time   O log d   where d is number of binary digits

User · Answer

bool isPowerOfTwo int x       register int bitpos  bitpos2    asm   bsrl  1  0     r   bitpos   rm   x       asm   bsfl  1  0     r   bitpos2   rm   x       return bitpos  gt  0  amp  amp  bitpos    bitpos2

User · Answer

bool IsPowerOfTwo int n                if  n  gt  1                        while  n 2    0                                n  gt  gt   1                                  return n    1          And here s a general algorithm for finding out if a number is a power of another number       bool IsPowerOf int n int b                if  n  gt  1                        while  n   b    0                                n    b                                  return n    1

User · Answer

This program in java returns  true  if number is a power of 2 and returns  false  if its not a power of 2     To check if the given number is power of 2  import java util Scanner   public class PowerOfTwo       int n      void solve             while true                To eleminate the odd numbers             if  n 2    0                   System out println  false                    break                    Tracing the number back till 2             n   n 2      2 2 gives one so condition should be 1             if n    1                    System out println  true                    break                                    public static void main String   args               TODO Auto-generated method stub         Scanner in   new Scanner System in           PowerOfTwo obj   new PowerOfTwo            obj n   in nextInt            obj solve              OUTPUT    34 false  16 true

User · Answer

I see many answers are suggesting to return n  amp  amp    n  amp   n - 1   but to my experience if the input values are negative it returns false values  I will share another simple approach here since we know a power of two number have only one set bit so simply we will count number of set bit this will take O log N  time   while  n  gt  0        int count   0      n   n  amp   n - 1       count      return count    1    Check this article to count no  of set bits

User · Answer

Find if the given number is a power of 2     include  lt math h gt   int main void        int n logval powval      printf  Enter a number to find whether it is s power of 2 n        scanf   d   amp n       logval log n  log 2       powval pow 2 logval        if powval  n          printf  The number is a power of 2        else         printf  The number is not a power of 2         getch        return 0

User · Answer

A number is a power of 2 if it contains only 1 set bit  We can use this property and the generic function countSetBits to find if a number is power of 2 or not   This is a C   program   int countSetBits int n            int c   0          while n                            c    1                  n    n  amp   n-1                     return c     bool isPowerOfTwo int n                    return  countSetBits n   1     int main         int i  val      0 1 2 3 4 5 15 16 22 32 38 64 70       for i 0  i lt sizeof val  sizeof val 0    i            printf  Num  d tSet Bits  d t is power of two   d n  val i   countSetBits val i    isPowerOfTwo val i         return 0      We dont need to check explicitly for 0 being a Power of 2  as it returns False for 0 as well   OUTPUT  Num 0   Set Bits 0   is power of two  0 Num 1   Set Bits 1   is power of two  1 Num 2   Set Bits 1   is power of two  1 Num 3   Set Bits 2   is power of two  0 Num 4   Set Bits 1   is power of two  1 Num 5   Set Bits 2   is power of two  0 Num 15  Set Bits 4   is power of two  0 Num 16  Set Bits 1   is power of two  1 Num 22  Set Bits 3   is power of two  0 Num 32  Set Bits 1   is power of two  1 Num 38  Set Bits 3   is power of two  0 Num 64  Set Bits 1   is power of two  1 Num 70  Set Bits 3   is power of two  0

User · Answer

in this approach   you can check if there is only 1 set bit in the integer and the integer is  gt  0  c     bool is pow of 2 int n       int count   0      for int i   0  i  lt  32  i             count     n gt  gt i  amp  1             return count    1  amp  amp  n  gt  0

User · Answer

Improving the answer of  user134548  without bits arithmetic   public static bool IsPowerOfTwo ulong n        if  n   2    0  return false      is odd  can t be power of 2       double exp   Math Log n  2       if  exp    Math Floor exp   return false      if exp is not integer  n can t be power     return Math Pow 2  exp     n      This works fine for   IsPowerOfTwo 9223372036854775809

User · Answer

In C  I tested the i  amp  amp    i  amp   i - 1  trick and compared it with   builtin popcount i   using gcc on Linux  with the -mpopcnt flag to be sure to use the CPU s POPCNT instruction  My test program counted the   of integers between 0 and 2 31 that were a power of two   At first I thought that i  amp  amp    i  amp   i - 1  was 10  faster  even though I verified that POPCNT was used in the disassembly where I used  builtin popcount   However  I realized that I had included an if statement  and branch prediction was probably doing better on the bit twiddling version  I removed the if and POPCNT ended up faster  as expected   Results   Intel R  Core TM  i7-4771 CPU max 3 90GHz  Timing  i  amp    i  amp   i - 1    trick 30  real    0m13 804s user    0m13 799s sys     0m0 000s  Timing POPCNT 30  real    0m11 916s user    0m11 916s sys     0m0 000s   AMD Ryzen Threadripper 2950X 16-Core Processor max 3 50GHz   Timing  i  amp  amp    i  amp   i - 1    trick 30  real    0m13 675s user    0m13 673s sys 0m0 000s  Timing POPCNT 30  real    0m13 156s user    0m13 153s sys 0m0 000s   Note that here the Intel CPU seems slightly slower than AMD with the bit twiddling  but has a much faster POPCNT  the AMD POPCNT doesn t provide as much of a boost   popcnt test c    include  stdio h      Count   of integers that are powers of 2 up to 2 31  int main       int n    for  int z   0  z  lt  20  z           n   0        for  unsigned long i   0  i  lt  1 lt  lt 30  i              ifdef USE POPCNT         n       builtin popcount i   1      Was  if    builtin popcount i     1  n            else         n     i  amp  amp    i  amp   i - 1         Was  if  i  amp  amp    i  amp   i - 1    n            endif                printf   d n   n     return 0      Run tests   gcc popcnt test c -O3 -o test exe gcc popcnt test c -O3 -DUSE POPCNT -mpopcnt -o test-popcnt exe  echo  Timing  i  amp  amp    i  amp   i - 1    trick  time   test exe  echo echo  Timing POPCNT  time   test-opt exe

User · Answer

Here is another method I devised  in this case using   instead of  amp     bool is power of 2 ulong x        if x      1  lt  lt   sizeof ulong  8 -1    return true      return  x  gt  0   amp  amp   x lt  lt 1     x  x-1    1

User · Answer

bool isPow2     x  amp    x-1    x     x   0

User · Answer

int isPowerOfTwo unsigned int x        return   x    0   amp  amp    x  amp    x   1      x        This is really fast  It takes about 6 minutes and 43 seconds to check all 2 32 integers

User · Answer

After posting the question I thought of the following solution   We need to check if exactly one of the binary digits is one  So we simply shift the number right one digit at a time  and return true if it equals 1  If at any point we come by an odd number   number  amp  1     1   we know the result is false  This proved  using a benchmark  slightly faster than the original method for  large  true values and much faster for false or small values   private static bool IsPowerOfTwo ulong number        while  number    0                if  number    1              return true           if   number  amp  1     1                 number is an odd number and not 1 - so it s not a power of two              return false           number   number  gt  gt  1            return false        Of course  Greg s solution is much better

User · Answer

return  i  amp  -i     i

User · Answer

return   x    0   amp  amp    x  amp   x - 1       If x is a power of two  its lone 1 bit is in position n  This means x     1 has a 0 in position n  To see why  recall how a binary subtraction works  When subtracting 1 from x  the borrow propagates all the way to position n  bit n becomes 0 and all lower bits become 1  Now  since x has no 1 bits in common with x     1  x  amp   x     1  is 0  and   x  amp   x     1   is true

User · Answer

There s a simple trick for this problem   bool IsPowerOfTwo ulong x        return  x  amp   x - 1      0      Note  this function will report true for 0  which is not a power of 2  If you want to exclude that  here s how   bool IsPowerOfTwo ulong x        return  x    0   amp  amp    x  amp   x - 1      0       Explanation  First and foremost the bitwise binary  amp  operator from MSDN definition      Binary  amp  operators are predefined for the integral types and bool  For   integral types   amp  computes the logical bitwise AND of its operands    For bool operands   amp  computes the logical AND of its operands  that   is  the result is true if and only if both its operands are true    Now let s take a look at how this all plays out   The function returns boolean  true   false  and accepts one incoming parameter of type unsigned long  x  in this case    Let us for the sake of simplicity assume that someone has passed the value 4 and called the function like so   bool b   IsPowerOfTwo 4    Now we replace each occurrence of x with 4   return  4    0   amp  amp    4  amp   4-1      0     Well we already know that 4    0 evals to true  so far so good   But what about     4  amp   4-1      0    This translates to this of course     4  amp  3     0    But what exactly is 4 amp 3   The binary representation of 4 is 100 and the binary representation of 3 is 011  remember the  amp  takes the binary representation of these numbers    So we have   100   4 011   3   Imagine these values being stacked up much like elementary addition  The  amp  operator says that if both values are equal to 1 then the result is 1  otherwise it is 0  So 1  amp  1   1  1  amp  0   0  0  amp  0   0  and 0  amp  1   0  So we do the math   100 011 ---- 000   The result is simply 0  So we go back and look at what our return statement now translates to   return  4    0   amp  amp    4  amp  3     0     Which translates now to   return true  amp  amp   0    0       return true  amp  amp  true    We all know that true  amp  amp  true is simply true  and this shows that for our example  4 is a power of 2

User · Answer

for any power of 2  the following also holds   n  -n   n  NOTE  fails for n 0   so need to check for it Reason why this works is  -n is the 2s complement of n  -n will have every bit to the left of rightmost set bit of n flipped compared to n  For powers of 2 there is only one set bit

User · Answer

Some sites that document and explain this and other bit twiddling hacks are    http   graphics stanford edu  seander bithacks html  http   graphics stanford edu  seander bithacks html DetermineIfPowerOf2  http   bits stephan-brumme com   http   bits stephan-brumme com isPowerOfTwo html    And the grandaddy of them  the book  Hacker s Delight  by Henry Warren  Jr     http   www hackersdelight org    As Sean Anderson s page explains  the expression   x  amp   x - 1      0  incorrectly indicates that 0 is a power of 2   He suggests to use      x  amp   x - 1    amp  amp  x    to correct that problem

User · Answer

This is another method to do it as well package javacore   import java util Scanner   public class Main exercise5       public static void main String   args               Local Declaration         boolean ispoweroftwo   false          int n          Scanner input   new Scanner  System in           System out println  quot Enter a number quot            n   input nextInt            ispoweroftwo   checkNumber n           System out println ispoweroftwo                  public static boolean checkNumber int n               Function declaration         boolean ispoweroftwo  false             if not divisible by 2  means isnotpoweroftwo         if n 2  0               ispoweroftwo false              return ispoweroftwo                    else               for int power 1  power gt 0  power power lt  lt 1                    if  power  n                        return true                                    else if  power gt n                        return false                                                    return ispoweroftwo

User · Answer

Mark gravell suggested this if you have  NET Core 3  System Runtime Intrinsics X86 Popcnt PopCount  public bool IsPowerOfTwo uint i        return Popcnt PopCount i     1     Single instruction  faster than  x    0   amp  amp    x  amp   x - 1      0  but less portable

User · Answer

bool IsPowerOfTwo ulong x        return x  gt  0  amp  amp   x  amp   x - 1      0

User · Answer

Here s a simple C   solution   bool IsPowerOfTwo  unsigned int i         return std  bitset lt 32 gt  i  count      1

[c#] How to check if a number is a power of 2

Further adding to the beauty of accepted answer above -

Examples related to c#

Examples related to algorithm

Examples related to math