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 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
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.
How to check if a number is a power of 2 in SWIFT
Determining if an integer is a power of 2
from the Bit Twiddling Hacks
is almost verbatim translated to Swift:
func isPowerOfTwo(_ n: Int) -> Bool {
return (n > 0) && (n & (n - 1) == 0)
}
Example:
print(isPowerOfTwo(4)) // true
print(isPowerOfTwo(5)) // false
Or as a generic function, so that it can be used with all binary
integer types:
func isPowerOfTwo<T: BinaryInteger> (_ n: T) -> Bool {
return (n > 0) && (n & (n - 1) == 0)
}
Example:
print(isPowerOfTwo(Int16(4))) // true
print(isPowerOfTwo(UInt8(5))) // false
Or as a protocol extension:
extension BinaryInteger {
var isPowerOfTwo: Bool {
return (self > 0) && (self & (self - 1) == 0)
}
}
Example:
print(1048576.isPowerOfTwo) // true
print(Int(50).isPowerOfTwo) // false
Related Topics
How to Enable Assembly Bind Failure Logging (Fusion) in .Net
Linq'S Distinct() on a Particular Property
How to Call Asynchronous Method from Synchronous Method in C#
What Is the Correct Way to Create a Single-Instance Wpf Application
What Are the Differences Between a Multidimensional Array and an Array of Arrays in C#
How to Generate a Random Integer in C#
Create Generic Method Constraining T to an Enum
How Would I Run an Async Task≪T≫ Method Synchronously
How To: Execute Command Line in C#, Get Std Out Results
How to Add User-Supplied Input to an SQL Statement
Windows Service Not Shown in Add Remove Programs Under Control Panel
The Calling Thread Cannot Access This Object Because a Different Thread Owns It
How to Dynamically Compile and Execute C# Code Fragments
Embedding Dlls in a Compiled Executable
What Are the Uses of "Using" in C#