How can I test whether a number is a power of 2?

Question

I need a function like this:

// return true if 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  
// is_power_of_2(3) => false
bool is_power_of_2(int n);

Can anyone suggest how I could write this?

Answer 1

(n & (n - 1)) == 0 is best. However, note that it will incorrectly return true for n=0, so if that is possible, you will want to check for it explicitly.

http://www.graphics.stanford.edu/~seander/bithacks.html has a large collection of clever bit-twiddling algorithms, including this one.

Answer 2

A power of two will have just one bit set (for unsigned numbers). Something like

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

Will work fine; one less than a power of two is all 1s in the less significant bits, so must AND to 0 bitwise.

As I was assuming unsigned numbers, the == 0 test (that I originally forgot, sorry) is adequate. You may want a > 0 test if you're using signed integers.

Answer 3

Powers of two in binary look like this:

1: 0001
2: 0010
4: 0100
8: 1000

Note that there is always exactly 1 bit set. The only exception is with a signed integer. e.g. An 8-bit signed integer with a value of -128 looks like:

10000000

So after checking that the number is greater than zero, we can use a clever little bit hack to test that one and only one bit is set.

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x−1));
}

For more bit twiddling see here.

Answer 4

In C++20 there is std::has_single_bit which you can use for exactly this purpose if you don't need to implement it yourself:

#include <bit>
static_assert(std::has_single_bit(16));
static_assert(!std::has_single_bit(15));

Note that this requires the argument to be an unsigned integer type.

Answer 5

Approach #1:

Divide number by 2 reclusively to check it.

Time complexity : O(log2n).

Approach #2:

Bitwise AND the number with its just previous number should be equal to ZERO.

Example: Number = 8 Binary of 8: 1 0 0 0 Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 0 0 0 0 = 0.

Time complexity : O(1).

Approach #3:

Bitwise XOR the number with its just previous number should be sum of both numbers.

Example: Number = 8 Binary of 8: 1 0 0 0 Binary of 7: 0 1 1 1 and the bitwise XOR of both the numbers is 1 1 1 1 = 15.

Time complexity : O(1).

http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html

Answer 6

bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

Answer 7

for any power of 2, the following also holds.

n&(-n)==n

NOTE: The condition is true for n=0 ,though its not a power of 2.
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.

Answer 8

This is probably the fastest, if using GCC. It only uses a POPCNT cpu instruction and one comparison. Binary representation of any power of 2 number, has always only one bit set, other bits are always zero. So we count the number of set bits with POPCNT, and if it's equal to 1, the number is power of 2. I don't think there is any possible faster methods. And it's very simple, if you understood it once:

if(1==__builtin_popcount(n))

Answer 9

return n > 0 && 0 == (1 << 30) % n;

Answer 10

Following would be faster then most up-voted answer due to boolean short-circuiting and fact that comparison is slow.

int isPowerOfTwo(unsigned int x)
{
  return x && !(x & (x – 1));
}

If you know that x can not be 0 then

int isPowerOfTwo(unsigned int x)
{
  return !(x & (x – 1));
}

Answer 11

This isn't the fastest or shortest way, but I think it is very readable. So I would do something like this:

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

This works since binary is based on powers of two. Any number with only one bit set must be a power of two.

Answer 12

What's the simplest way to test whether a number is a power of 2 in C++?

If you have a modern Intel processor with the Bit Manipulation Instructions, then you can perform the following. It omits the straight C/C++ code because others have already answered it, but you need it if BMI is not available or enabled.

bool IsPowerOf2_32(uint32_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u32(x));
#endif
    // Fallback to C/C++ code
}

bool IsPowerOf2_64(uint64_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u64(x));
#endif
    // Fallback to C/C++ code
}

GCC, ICC, and Clang signal BMI support with __BMI__. It's available in Microsoft compilers in Visual Studio 2015 and above when AVX2 is available and enabled. For the headers you need, see Header files for SIMD intrinsics.

I usually guard the _blsr_u64 with an _LP64_ in case compiling on i686. Clang needs a little workaround because it uses a slightly different intrinsic symbol nam:

#if defined(__GNUC__) && defined(__BMI__)
# if defined(__clang__)
#  ifndef _tzcnt_u32
#   define _tzcnt_u32(x) __tzcnt_u32(x)
#  endif
#  ifndef _blsr_u32
#    define  _blsr_u32(x)  __blsr_u32(x)
#  endif
#  ifdef __x86_64__
#   ifndef _tzcnt_u64
#    define _tzcnt_u64(x) __tzcnt_u64(x)
#   endif
#   ifndef _blsr_u64
#     define  _blsr_u64(x)  __blsr_u64(x)
#   endif
#  endif  // x86_64
# endif  // Clang
#endif  // GNUC and BMI

---

Can you tell me a good web site where this sort of algorithm can be found?

This website is often cited: Bit Twiddling Hacks.

Answer 13

Here is another method, in this case using | instead of & :

bool is_power_of_2(int x) {
    return x > 0 && (x<<1 == (x|(x-1)) +1));
}

Answer 14

It is possible through c++

int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}

Answer 15

Another way to go (maybe not fastest) is to determine if ln(x) / ln(2) is a whole number.

Answer 16

This is the bit-shift method in T-SQL (SQL Server):

SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo

It is a lot faster than doing a logarithm four times (first set to get decimal result, 2nd set to get integer set & compare)