What's the simplest way to test whether a numb

Question

I need a function like this:

// return true iff '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? Can you tell me a good web site where this sort of algorithm can be found?

Answer 1

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 2

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 3

This is the fastest:

if(1==__builtin_popcount(n))

Answer 4

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 5

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 6

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)