What is the easiest way to check if a number is a power of 2 in C ++?

Question

I need a function like this:

// return true iff 'n' is a power of 2, eg // 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 website where you can find such an algorithm?

Answer 1

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

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

Answer 2

The power of two will have only one bit (for unsigned numbers). Something like

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

Will work fine; one is less than two, it's all 1s in less significant bits, so AND should be 0 bitwise.

Since I was accepting unsigned numbers, the test == 0 (which I initially forgot, sorry) is enough. You may need a test> 0 if you use signed integers.

Answer 3

The forces of the two in binary form are as follows:

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

Note that exactly 1 bit always exists. The only exception is the signed integer. for example, an 8-bit signed integer with a value of -128 looks like this:

 10000000 

So, after verifying that the number is greater than zero, we can use the smart bit hack to verify that one and only one bit is set.

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

For a more detailed view, see here .

Answer 4

Approach No. 1:

Divide the number by 2 to check it.

Difficulty of time: O (log2n).

Approach No. 2:

The bitwise AND number with its only previous number should be equal to ZERO.

Example: Number = 8 Binary code 8: 1 0 0 0 Binary number 7: 0 1 1 1 and bitwise And both numbers are 0 0 0 0 = 0.

Difficulty of time: O (1).

Approach No. 3:

The bitwise XOR number with only its previous number should be the sum of both numbers.

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

Difficulty of time: O (1).

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

Answer 5

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

Answer 6

for any degree 2, the following is also true.

n & (- n) == n

NOTE. The condition is true for n = 0, although its value is not equal to 2.
The reason why this works:
-n is the 2s complement to n. -n will have every bit to the left of the rightmost set of bits n flipped compared to n. For degrees 2, there is only one set bit.

Answer 7

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

Answer 8

After that, it will be faster than most of the answers polled due to the Boolean short circuit and the fact of slow comparison.

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

If you know that x cannot be 0, then

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

Answer 9

What is the easiest way to check if a number is a power of 2 in C ++?

If you have a modern Intel processor with bit management instructions , you can do the following. It skips the direct C / C ++ code because others have already answered it, but you need it if the BMI is not available or not 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 is available on Microsoft compilers in Visual Studio 2015 and later when AVX2 is available and enabled . See the header files for the built-in SIMD functions for the necessary headers .

I usually _blsr_u64 with _LP64_ in case of compilation on i686. Clang needs a little workaround because it uses a slightly different internal nam character:

 #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 website where you can find such an algorithm?

This site is often cited: Bit Twiddling Hacks .

Answer 10

This is not the fastest or shortest path, 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 because the binary is based on powers of two. Any number with only one set of bits must have a power of two.

Answer 11

This is the fastest:

 if(1==__builtin_popcount(n)) 

Answer 12

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 13

It is possible with C ++

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

Answer 14

In C ++ 20, there is std::ispow2 which you can use for this purpose, if you do not need to implement it yourself:

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

Answer 15

Another way (perhaps not the fastest) is to determine if ln (x) / ln (2) is an integer.

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 

This is much faster than doing the logarithm four times (first set to get a decimal result, 2nd set to get an integer set and compare)