How to check if a number is a power of 2
There's a simple trick for this problem:
bool IsPowerOfTwo(ulong x)
{
return (x & (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) && ((x & (x - 1)) == 0);
}
Explanation
First and foremost the bitwise binary & operator from MSDN definition:
Binary & operators are predefined for the integral types and bool. For
integral types, & computes the logical bitwise AND of its operands.
For bool operands, & 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) && ((4 & (4-1)) == 0);
Well we already know that 4 != 0 evals to true, so far so good. But what about:
((4 & (4-1)) == 0)
This translates to this of course:
((4 & 3) == 0)
But what exactly is 4&3
?
The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & 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 &
operator says that if both values are equal to 1 then the result is 1, otherwise it is 0. So 1 & 1 = 1
, 1 & 0 = 0
, 0 & 0 = 0
, and 0 & 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) && ((4 & 3) == 0);
Which translates now to:
return true && (0 == 0);
return true && true;
We all know that true && true
is simply true
, and this shows that for our example, 4 is a power of 2.
How to check if a given number is a power of two?
Bit Manipulations
One approach would be to use bit manipulations:
(n & (n-1) == 0) and n != 0
Explanation: every power of 2 has exactly 1 bit set to 1 (the bit in that number's log base-2 index). So when subtracting 1 from it, that bit flips to 0 and all preceding bits flip to 1. That makes these 2 numbers the inverse of each other so when AND-ing them, we will get 0 as the result.
For example:
n = 8
decimal | 8 = 2**3 | 8 - 1 = 7 | 8 & 7 = 0
| ^ | |
binary | 1 0 0 0 | 0 1 1 1 | 1 0 0 0
| ^ | | & 0 1 1 1
index | 3 2 1 0 | | -------
0 0 0 0
-----------------------------------------------------
n = 5
decimal | 5 = 2**2 + 1 | 5 - 1 = 4 | 5 & 4 = 4
| | |
binary | 1 0 1 | 1 0 0 | 1 0 1
| | | & 1 0 0
index | 2 1 0 | | ------
1 0 0
So, in conclusion, whenever we subtract one from a number, AND the result with the number itself, and that becomes 0 - that number is a power of 2!
Of course, AND-ing anything with 0
will give 0, so we add the check for n != 0
.
math
functions
You could always use math functions, but notice that using them without care could cause incorrect results:
math.log(x[, base])
withbase=2
:import math
math.log(n, 2).is_integer()math.log2(x)
:math.log2(n).is_integer()
Worth noting that for any n <= 0
, both functions will throw a ValueError
as it is mathematically undefined (and therefore shouldn't present a logical problem).
math.frexp(x)
:abs(math.frexp(n)[0]) == 0.5
As noted above, for some numbers these functions are not accurate and actually give FALSE RESULTS:
math.log(2**29, 2).is_integer()
will giveFalse
math.log2(2**49-1).is_integer()
will giveTrue
math.frexp(2**53+1)[0] == 0.5
will giveTrue
!!
This is because math
functions use floats, and those have an inherent accuracy problem.
(Expanded) Timing
Some time has passed since this question was asked and some new answers came up with the years. I decided to expand the timing to include all of them.
According to the math docs, the log
with a given base, actually calculates log(x)/log(base)
which is obviously slow. log2
is said to be more accurate, and probably more efficient. Bit manipulations are simple operations, not calling any functions.
So the results are:
Ev: 0.28 sec
log
withbase=2
: 0.26 seccount_1: 0.21 sec
check_1: 0.2 sec
frexp
: 0.19 sec
log2
: 0.1 secbit ops: 0.08 sec
The code I used for these measures can be recreated in this REPL (forked from this one).
How to test if a number is a power of 2?
Haskell has bitwise operations, but these have a slightly different name. Indeed, you can make a bitwise AND with the (.&.) :: Bits a => a -> a -> a
function.
You thus can make such check with:
import Data.Bits(Bits, (.&.))
isPower2 :: (Bits i, Integral i) => i -> Bool
isPower2 n = n .&. (n-1) == 0
Note that your proposed solution will include zero as a power of two as well. Indeed, if we evaluate the first 1'000 numbers, we get:
Prelude Data.Bits> filter isPower2 [0 .. 1000]
[0,1,2,4,8,16,32,64,128,256,512]
How to check if a number 1 is power of 2?
Try this solution:
public boolean isPowerOf2(float number){
if(number>1){
//easy to write
}else if(number==1){
return true;
}else if(number>0){
return isPowerOf2(1.0f/number);
}else
return false;
}
By the way you can solve this simply by checking the bits of float binary representation:
public static boolean isPowerOfTwo(float i) {
int bits = Float.floatToIntBits(i);
if((bits & ((1 << 23)-1)) != 0)
return ((bits & (bits-1)) == 0); // denormalized number
int power = bits >>> 23;
return power > 0 && power < 255; // 255 = Infinity; higher values = negative numbers
}
What is the best way to determine if a given number is a power of two?
You can actually use ECMAScript5 Math.log
:
function powerOfTwo(x) {
return (Math.log(x)/Math.log(2)) % 1 === 0;
}
Remember, in math, to get a logarithm with an arbitrary base, you can just divide log10 of the operand (x
in this case) by log10 of the base. And then to see if the number is a regular integer (and not a floating point), just check if the remainder is 0 by using the modulus %
operator.
In ECMAScript6 you can do something like this:
function powerOfTwo(x) {
return Math.log2(x) % 1 === 0;
}
See the MDN docs for Math.log2
.
Find if a number is a power of two without math function or log function
You can test if a positive integer n
is a power of 2 with something like
(n & (n - 1)) == 0
If n
can be non-positive (i.e. negative or zero) you should use
(n > 0) && ((n & (n - 1)) == 0)
If n
is truly a power of 2, then in binary it will look like:
10000000...
so n - 1
looks like
01111111...
and when we bitwise-AND them:
10000000...
& 01111111...
-----------
00000000...
Now, if n
isn't a power of 2, then its binary representation will have some other 1s in addition to the leading 1, which means that both n
and n - 1
will have the same leading 1 bit (since subtracting 1 cannot possibly turn off this bit if there is another 1 in the binary representation somewhere). Hence the &
operation cannot produce 0
if n
is not a power of 2, since &
ing the two leading bits of n
and n - 1
will produce 1
in and of itself. This of course assumes that n
is positive.
This is also explained in "Fast algorithm to check if a positive number is a power of two" on Wikipedia.
Quick sanity check:
for (int i = 1; i <= 100; i++) {
if ((i & (i - 1)) == 0)
System.out.println(i);
}
1
2
4
8
16
32
64
Finding if a number is a power of 2
One way is to use bitwise AND. If a number $x
is a power of two (e.g., 8=1000), it will have no bits in common with its predecessor (7=0111). So you can write:
($x & ($x - 1)) == 0
Note: This will give a false positive for $x == 0.
How does this bitwise operation check for a power of 2?
Any power of 2 minus 1 is all ones: (2 N - 1 = 111....b)
2 = 2^1. 2-1 = 1 (1b)
4 = 2^2. 4-1 = 3 (11b)
8 = 2^3. 8-1 = 7 (111b)
Take 8 for example. 1000 & 0111 = 0000
So that expression tests if a number is NOT a power of 2.
Related Topics
Getting a List of User Profiles on a Computer in C++ Win32
How Do C++ Progs Get Their Return Value, When a Return Is Not Specified in the Function
Constexpr Class Taking Const References Not Compiling
C++ CSV Line with Commas and Strings Within Double Quotes
How Does Url Within Function Body Get Compiled
Undefined Behavior in C/C++: I++ + ++I VS ++I + I++
How to Send Keystrokes to a Window
How to Swap Array-Elements to Transfer the Array from a Column-Like into a Row-Like Representation
Splice() on Std::List and Iterator Invalidation
How Does Std::Vector Support Contiguous Memory for Custom Objects of Unknown Size
Does Std::Bind Work with Move-Only Types in General, and Std::Unique_Ptr in Particular
Mixing Ifstream Getline and >>
Throw and Ternary Operator in C++
How to Do Performance Test Using the Boost Library for a Custom Library
Why Does Std::Vector Work with Incomplete Types in Class Definitions