How to check if a number is a power of 2

Question

Today I needed a simple algorithm for checking if a number is a power of 2.

The algorithm needs to be:

1. Simple
2. Correct for any ulong value.

I came up with this simple algorithm:

private bool IsPowerOfTwo(ulong number)
{
    if (number == 0)
        return false;

    for (ulong power = 1; power > 0; power = power << 1)
    {
        // This for loop used shifting for powers of 2, meaning
        // that the value will become 0 after the last shift
        // (from binary 1000...0000 to 0000...0000) then, the 'for'
        // loop will break out.

        if (power == number)
            return true;
        if (power > number)
            return false;
    }
    return false;
}

But then I thought: How about checking if log₂ x is an exactly a round number? When I checked for 2^63+1, Math.Log() returned exactly 63 because of rounding. So I checked if 2 to the power 63 is equal to the original number and it is, because the calculation is done in doubles and not in exact numbers.

private bool IsPowerOfTwo_2(ulong number)
{
    double log = Math.Log(number, 2);
    double pow = Math.Pow(2, Math.Round(log));
    return pow == number;
}

This returned true for the given wrong value: 9223372036854775809.

Is there a better algorithm?

Chandos

I think the solution (x & (x - 1)) may return false positives when X is a sum of powers of two, e.g. 8 + 16. – Pointdevice

All numbers can be written as a sum of powers of two, it's why we can represent any number in binary. Furthermore, your example does not return a false positive, because 11000 & 10111 = 10000 != 0. – Exeunt

@JoeBrown It doesn't have any false positives. In fact the expression returns the larger of any sum of two powers of two. – Ithaca

It’s very easy in .net 6 now https://mcmap.net/q/63384/-how-to-check-if-a-number-is-a-power-of-2 – Fenestrated

Won't every power of two only have one set bit? 2^0 = 1 , 2^1 = 10, 2^2 = 100, 2^3 = 1000 and so on So can't we just check if there is just one set bit? 2 ^x = Sum(0 x 2^xi) + (1 x 2 ^ x) + Sum(0 x 2 ^xj) – Tittup

@Tittup And how do you do that? That's what the answers address. – Inactivate

Answer 1

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.

Marshmallow

@Kripp: The number will be of the binary form 1000...000. When you -1 it, it will be of the form 0111...111. Thus, the two number's binary and would result is 000000. This wouldn't happen for non-power-of-twos, since 1010100 for example would become 1010011, resulting in an (continued...) – Chandos

... Resulting in a 1010000 after the binary and. The only false positive would be 0, which is why I would use: return (x != 0) && ((x & (x - 1)) == 0); – Chandos

Kripp, consider (2:1, 10:1) (4:3, 100:11) (8:7, 1000:111) (16:15, 10000:1111) See the pattern? – Wahlstrom

it relies on twos complement. since that is almost universal now this it not a problem but I mention it for completeness... – Kuehl

@ShuggyCoUk: two's complement is how negative numbers are represented. Since this is an unsigned integer, representation of negative numbers is not relevant. This technique only relies on binary representation of nonnegative integers. – Marshmallow

@ShuggyCoUk: Where's the problem with relying on two's complement here? The only value I can think of that would misbehave is Int(16/32/64).MinValue, right? So you simply change x != 0 to x > 0 and the answer is correct – Chandos

Because comments are finicky things (and may be deleted), I've added what is in the comments to the answer as an Editor's Note. – Matildamatilde

@George Stocker: In C/C++ your editors note will be faster for non-powers of two if the x != 0 is placed on the right side instead of the left side. That way, when x is not a power of two, it will not be compared to 0. – Hairdresser

@SoapBox: Not necessarily. You are still checking either way. The difference is one over the other. – Mediocre

@Hairdresser - what is more common? Zeroes or non-zero numbers which aren't powers of two? This is a question you can't answer without some more context. And it really, really doesn't matter anyway. – Chandos

Statistically, zero is less common than the other 4 billion numbers which are not powers of two. So for 4 billion cases you'll be making two comparisons where one would work. It does make a difference, because in C and C++ the right hand side won't even be checked if the left side is false. So you're saving a comparison. It's not a big deal, but it is easy enough to think about when reading and writing code there's no reason not to do it. – Hairdresser

@SoapBox: if you go at that kind of micro optimization, it would probably be even faster than both orders to use a single & instead of &&. As we are dealing with booleans it will yield the same result, but & does not defines a sequence point, which has usually a high cost (well, really we would have to measure to be sure it makes any difference). – Morganstein

@kriss: This isn't C++. Sequence points don't exist in the same form in C#, they're defined by the jitter with relation to which data is being used as opposed to which operators; as far as the developer is concerned, both & and && define a sequence point, but && is short-circuiting. – Chandos

That said, it's possible that short-circuiting would cause jumps in the generated assembly and using & would not; you'd really have to measure to see if there's any difference. – Chandos

May I suggest a branchless version that correctly filters 0? It's this: ((x | 0x8000000000000000) & (x - 1)) == 0. The reason this works can be found here. – Tropical

@nightcracker: for 16-, 32-, 64- and whatever-bit integers? – Velvety

@snemarch: that's for 64-bit integers (as specified in the question). 16-bit uses 0x8000, 32-bit is 0x80000000. So, in general, for n-bit use 1 << (n - 1). – Tropical

Why does this function return -1 instead of 1 on success? – Canteen

Is there something similar to this that can determine if a number is a power of 3? 5? etc? – Inning

@JohnOdom: Not as simple, but check How to check if an integer is power of 3?. There's probably also something you can find for 5. – Marshmallow

Shouldn't the order of conditions be reversed? ((x & (x - 1)) == 0 && (x != 0) should be more efficient under normal conditions - intuition tells me that zero will be rarely checked. Of course I have no data to proof my point – Kaki

your solution will fail a testcase of -2147483648 – Commode

@Antz_shrek: No, because the parameter type is ulong, which is unsigned. – Marshmallow

How come the & for operands binary solves the issue ! any more explanation why 000 means its power of two, what if i asked for check if its power of 3 what dose that change thanks. – Astra

@Astra check this answer https://mcmap.net/q/63384/-how-to-check-if-a-number-is-a-power-of-2 – Fleshings

@GregHewgill It will not work for x=1, willn't it? Maybe it would be better to use (x > 1) && ((x & (x - 1)) == 0) ? – Sydel

@Galina: It works just fine for x=1, since 1 & 0 == 0 and 1 is a power of 2. – Marshmallow

Why not x && !(x & (x - 1)) though? Oh, never mind, it was a C# question. – Sicken

It’s very easy now in .net 6 https://mcmap.net/q/63384/-how-to-check-if-a-number-is-a-power-of-2 – Fenestrated

@Astra A good way to explain it is that all powers of two are represented by a single, lonely bit, and reducing it by one necessarily eliminates that bit. No bits left in their original position means a zero AND result. All other numbers have more than one bit, and subtracting one will only move or remove one of them. That guarantees you always have at least one bit left in its original position, and consequently a non-zero AND result. – Wistful

Re: "this function will report true for 0, which is not a power of 2": hence, the name IsPowerOfTwo is misleading. It can be IsPowerOfTwoOrZero. – Unknit

Answer 2

Some sites that document and explain this and other bit twiddling hacks are:

• http://graphics.stanford.edu/~seander/bithacks.html
  (http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
• http://bits.stephan-brumme.com/
  (http://bits.stephan-brumme.com/isPowerOfTwo.html)

And the grandaddy of them, the book "Hacker's Delight" by Henry Warren, Jr.:

• http://www.hackersdelight.org/

As Sean Anderson's page explains, the expression ((x & (x - 1)) == 0) incorrectly indicates that 0 is a power of 2. He suggests to use:

(!(x & (x - 1)) && x)

to correct that problem.

Love

0 is a power of 2... 2 ^ -inf = 0. ;) ;) ;) – Biles

Since this is a C# tagged thread, it is worth pointing out that the last expression (of Sean Anderson) is illegal in C# since ! can only be applied to boolean types, and && also requires both operands to be boolean- (Except that user defined operators make other things possible, but that is not relevant for ulong.) – Drayton

catonmat.net/low-level-bit-hacks explains some related bithacks with 8-bit examples. e.g. Isolate the rightmost 1-bit with y = x & (-x). This test is just a special case of clearing the lowest set bit. – Vex

Answer 3

return (i & -i) == i

Inebriant

any hint why this will or will not work? i checked its correctness in java only, where there are only signed ints/longs. if it is correct, this would be the superior answer. faster+smaller – Inebriant

It takes advantage of one of the properties of two's-complement notation: to calculate the negative value of a number you perform a bitwise negation and add 1 to the result. The least significant bit of i which is set will also be set in -i. The bits below that will be 0 (in both values) while the bits above it will be inverted with respect to each other. The value of i & -i will therefore be the least significant set bit in i (which is a power of two). If i has the same value then that was the only bit set. It fails when i is 0 for the same reason that i & (i - 1) == 0 does. – Goof

If i is an unsigned type, twos complement has nothing to do with it. You're merely taking advantage of the properties of modular arithmetic and bitwise and. – Hessler

This doesn't work if i==0 (returns (0&0==0) which is true). It should be return i && ( (i&-i)==i ) – Kuomintang

Answer 4

The following addendum to the accepted answer may be useful for some people:

A power of two, when expressed in binary, will always look like 1 followed by n zeroes where n is greater than or equal to 0. Ex:

Decimal  Binary
1        1     (1 followed by 0 zero)
2        10    (1 followed by 1 zero)
4        100   (1 followed by 2 zeroes)
8        1000  (1 followed by 3 zeroes)
.        .
.        .
.        .

and so on.

When we subtract 1 from these kind of numbers, they become 0 followed by n ones and again n is same as above. Ex:

Decimal    Binary
1 - 1 = 0  0    (0 followed by 0 one)
2 - 1 = 1  01   (0 followed by 1 one)
4 - 1 = 3  011  (0 followed by 2 ones)
8 - 1 = 7  0111 (0 followed by 3 ones)
.          .
.          .
.          .

and so on.

Coming to the crux

What happens when we do a bitwise AND of a number x, which is a power of 2, and x - 1?

The one of x gets aligned with the zero of x - 1 and all the zeroes of x get aligned with ones of x - 1, causing the bitwise AND to result in 0. And that is how we have the single line answer mentioned above being right.

---

Further adding to the beauty of accepted answer above -

So, we have a property at our disposal now:

When we subtract 1 from any number, then in the binary representation the rightmost 1 will become 0 and all the zeroes to the right of that rightmost 1 will now become 1.

One awesome use of this property is in finding out - How many 1s are present in the binary representation of a given number? The short and sweet code to do that for a given integer x is:

byte count = 0;
for ( ; x != 0; x &= (x - 1)) count++;
Console.Write("Total ones in the binary representation of x = {0}", count);

---

Another aspect of numbers that can be proved from the concept explained above is "Can every positive number be represented as the sum of powers of 2?".

Yes, every positive number can be represented as the sum of powers of 2. For any number, take its binary representation. Ex: Take number 117.

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 1

Woodrum

Yes, by putting 0 as an example and making that math on it inside that binary representation. It creates a Confusion. – Wertheimer

For the "property", did you mean to say "... and all the zeros to the right of that rightmost 1 will now become 1"? – Basilbasilar

@lesterfernandez: You are correct! – Woodrum

Answer 5

bool IsPowerOfTwo(ulong x)
{
    return x > 0 && (x & (x - 1)) == 0;
}

Caen

This solution is better because it can also deal with negative number if negative were able to pass in. (if long instead of ulong) – Clair

Why does a decimal pass as a power of two in this case? – Milkwort

Answer 6

Here's a simple C++ solution:

bool IsPowerOfTwo( unsigned int i )
{
    return std::bitset<32>(i).count() == 1;
}

Ironmonger

on gcc this compiles down to a single gcc builtin called __builtin_popcount. Unfortunately, one family of processors doesn't yet have a single assembly instruction to do this (x86), so instead it's the fastest method for bit counting. On any other architecture this is a single assembly instruction. – Ironmonger

@Ironmonger newer x86 microarchitectures support popcnt – Medardas

lea eax, [rdi-1] + test/jnz to implement i & (i-1) == 0 is somewhat cheaper than popcnt / cmp/je, especially if you don't need to handle the i==0 case as not counting. – Vex

Thank you for mentioning C++ and linking it to C++'s wikipedia page. Without that it would have been really really confusing. /s – Woodrum

Answer 7

After posting the question I thought of the following solution:

We need to check if exactly one of the binary digits is one. So we simply shift the number right one digit at a time, and return true if it equals 1. If at any point we come by an odd number ((number & 1) == 1), we know the result is false. This proved (using a benchmark) slightly faster than the original method for (large) true values and much faster for false or small values.

private static bool IsPowerOfTwo(ulong number)
{
    while (number != 0)
    {
        if (number == 1)
            return true;

        if ((number & 1) == 1)
            // number is an odd number and not 1 - so it's not a power of two.
            return false;

        number = number >> 1;
    }
    return false;
}

---

Of course, Greg's solution is much better.

Chandos

Answer 8

    bool IsPowerOfTwo(int n)
    {
        if (n > 1)
        {
            while (n%2 == 0)
            {
                n >>= 1;
            }
        }
        return n == 1;
    }

And here's a general algorithm for finding out if a number is a power of another number.

    bool IsPowerOf(int n,int b)
    {
        if (n > 1)
        {
            while (n % b == 0)
            {
                n /= b;
            }
        }
        return n == 1;
    }

Clovah

Answer 9

It's very easy in .Net 6 now.

using System.Numerics;

bool isPow2 = BitOperations.IsPow2(64); // sets true

Here is the documentation.

Fenestrated

Answer 10

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

Azotemia

Is this c#? I guess this is c++ as x is returned as a bool. – Tedric

I did write it as C++. To make it C# is trivial: bool isPow2 = ((x & ~(x-1))==x)? x!=0 : false; – Azotemia

Answer 11

int isPowerOfTwo(unsigned int x)
{
    return ((x != 0) && ((x & (~x + 1)) == x));
}

This is really fast. It takes about 6 minutes and 43 seconds to check all 2^32 integers.

Responsiveness

Answer 12

return ((x != 0) && !(x & (x - 1)));

If x is a power of two, its lone 1 bit is in position n. This means x – 1 has a 0 in position n. To see why, recall how a binary subtraction works. When subtracting 1 from x, the borrow propagates all the way to position n; bit n becomes 0 and all lower bits become 1. Now, since x has no 1 bits in common with x – 1, x & (x – 1) is 0, and !(x & (x – 1)) is true.

Alpenhorn

Answer 13

bool isPowerOfTwo(int x_)
{
  register int bitpos, bitpos2;
  asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_));
  asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_));
  return bitpos > 0 && bitpos == bitpos2;
}

Hulk

bitpos > 0 is not a meaningful test if you're trying to exclude x_ == 0. An input of x_ = 1 has one set bit, and results in BSF and BSR producing a bit-position result of 0. You didn't initialize your "+r" read-write outputs so you don't have any guaranteed behaviour for x_ == 0. (BSF and BSR leave the destination unmodified on input=0; AMD documents this, Intel implements it but only documents the result as a undefined value.) Perhaps bitpos = 0, bitpos2 = 32 before the asm statements would be useful, so they mismatch on input=0. – Vex

I'd also suggest dropping the "m" from the input constraint. You want the compiler to pick a register because you're reading it twice. The 2nd asm statement could maybe be arranged so output=input initially so the compiler can pick the same register for input and output if it wants to. – Vex

asm is not cross-platform compatible. You didn't even mention what processor family this is valid for. – Exploratory

Answer 14

for any power of 2, the following also holds.

n&(-n)==n

NOTE: fails for n=0 , so need to check for it
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.

Publication

This answer was posted 7 years earlier. – Emmalynn

Answer 15

Find if the given number is a power of 2.

#include <math.h>

int main(void)
{
    int n,logval,powval;
    printf("Enter a number to find whether it is s power of 2\n");
    scanf("%d",&n);
    logval=log(n)/log(2);
    powval=pow(2,logval);

    if(powval==n)
        printf("The number is a power of 2");
    else
        printf("The number is not a power of 2");

    getch();
    return 0;
}

Koonce

Or, in C#: return x == Math.Pow(2, Math.Log(x, 2)); – Chandos

Broken. Suffers from major floating point rounding issues. Use frexp rather than nasty log stuff if you want to use floating point. – Hessler

Answer 16

A number is a power of 2 if it contains only 1 set bit. We can use this property and the generic function countSetBits to find if a number is power of 2 or not.

This is a C++ program:

int countSetBits(int n)
{
        int c = 0;
        while(n)
        {
                c += 1;
                n  = n & (n-1);
        }
        return c;
}

bool isPowerOfTwo(int n)
{        
        return (countSetBits(n)==1);
}
int main()
{
    int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70};
    for(i=0; i<sizeof(val)/sizeof(val[0]); i++)
        printf("Num:%d\tSet Bits:%d\t is power of two: %d\n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i]));
    return 0;
}

We dont need to check explicitly for 0 being a Power of 2, as it returns False for 0 as well.

OUTPUT

Num:0   Set Bits:0   is power of two: 0
Num:1   Set Bits:1   is power of two: 1
Num:2   Set Bits:1   is power of two: 1
Num:3   Set Bits:2   is power of two: 0
Num:4   Set Bits:1   is power of two: 1
Num:5   Set Bits:2   is power of two: 0
Num:15  Set Bits:4   is power of two: 0
Num:16  Set Bits:1   is power of two: 1
Num:22  Set Bits:3   is power of two: 0
Num:32  Set Bits:1   is power of two: 1
Num:38  Set Bits:3   is power of two: 0
Num:64  Set Bits:1   is power of two: 1
Num:70  Set Bits:3   is power of two: 0

Cleanlimbed

returning c as an 'int' when the function has a return type of 'ulong'? Using a while instead of an if? I personally can't see a reason but it would seem to work. EDIT:- no ... it will return 1 for anything greater than 0!? – Mae

@JamesKhoury I was writing a c++ program so I mistakingly returned an int. However that was a small typos and didn't deserved a downvote. But I fail to understand the reasoning for the rest of your comment "using while instead of if" and "it will return 1 for anything greater than 0". I added the main stub to check the output. AFAIK its the expected output. Correct me if I am wrong. – Cleanlimbed

Answer 17

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

bool is_power_of_2(ulong x) {
    if(x ==  (1 << (sizeof(ulong)*8 -1) ) return true;
    return (x > 0) && (x<<1 == (x|(x-1)) +1));
}

Amphibole

Do you need the (x > 0) bit here? – Chandos

@configurator, yes, otherwise is_power_of_2(0) would return true – Amphibole

Answer 18

I've been reading the documentation for Random.nextInt(int bound) and saw this nice piece of code which checks whether the parameter is a power of 2, which says (part of the code) :

if ((bound & -bound) == bound) // ie, bound is a power of 2   

let's test it

for (int i=0; i<=8; i++) {
  System.out.println(i+" = " + Integer.toBinaryString(i));
}

>>
0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
7 = 111
8 = 1000
// the left most 0 bits where cut out of the output

for (int i=-1; i>=-8; i--) {
  System.out.println(i+" = " + Integer.toBinaryString(i));
}

>>
-1 = 11111111111111111111111111111111
-2 = 11111111111111111111111111111110
-3 = 11111111111111111111111111111101
-4 = 11111111111111111111111111111100
-5 = 11111111111111111111111111111011
-6 = 11111111111111111111111111111010
-7 = 11111111111111111111111111111001
-8 = 11111111111111111111111111111000

did you notice something ? positive and negative Power 2 numbers have opposite bits in binary representation (negative power 2 numbers are 1's complement of positive power 2 numbers.

if we apply a logical AND over X and -X, where X is a Power 2 number, we get the same positive value X as a result :)

for (int i=0; i<=8; i++) {
  System.out.println(i + " & " + (-i)+" = " + (i & (-i)));
}

>>
0 & 0 = 0    <-
1 & -1 = 1   <-
2 & -2 = 2   <-
3 & -3 = 1
4 & -4 = 4   <-
5 & -5 = 1
6 & -6 = 2
7 & -7 = 1
8 & -8 = 8   <-

Visual

Answer 19

Example

0000 0001    Yes
0001 0001    No

Algorithm

1. Using a bit mask, divide NUM the variable in binary

2. IF R > 0 AND L > 0: Return FALSE

3. Otherwise, NUM becomes the one that is non-zero

4. IF NUM = 1: Return TRUE

5. Otherwise, go to Step 1

Complexity

Time ~ O(log(d)) where d is number of binary digits

Exhaust

Answer 20

Mark gravell suggested this if you have .NET Core 3, System.Runtime.Intrinsics.X86.Popcnt.PopCount

public bool IsPowerOfTwo(uint i)
{
    return Popcnt.PopCount(i) == 1
}

Single instruction, faster than (x != 0) && ((x & (x - 1)) == 0) but less portable.

Oxymoron

are you sure it's faster than (x != 0) && ((x & (x - 1)) == 0)? I doubt that, esp. on older systems where popcnt isn't available – Medardas

It's not faster. I just tested this on a modern Intel CPU and verified POPCNT in use in the disassembly (granted, in C code, not .NET). POPCNT is faster for counting bits in general, but for the single-bit-on case the bit twiddling trick is still faster by 10%. – Tetramethyldiarsine

Oops, I take it back. I was testing in a loop were I think branch prediction was "cheating". POPCNT is indeed a single instruction that runs in a single clock cycle and is faster if you have it available. – Tetramethyldiarsine

Answer 21

There is a one liner in .NET 6

// IsPow2 evaluates whether the specified Int32 value is a power of two.
Console.WriteLine(BitOperations.IsPow2(128));            // True

Yardstick

IsPow2 was already answer long before you – Medardas

Answer 22

Improving the answer of @user134548, without bits arithmetic:

public static bool IsPowerOfTwo(ulong n)
{
    if (n % 2 != 0) return false;  // is odd (can't be power of 2)

    double exp = Math.Log(n, 2);
    if (exp != Math.Floor(exp)) return false;  // if exp is not integer, n can't be power
    return Math.Pow(2, exp) == n;
}

This works fine for:

IsPowerOfTwo(9223372036854775809)

Yang

floating point operations are far slower than a simple bitwise expression – Medardas

Answer 23

in this approach , you can check if there is only 1 set bit in the integer and the integer is > 0 (c++).

bool is_pow_of_2(int n){
    int count = 0;
    for(int i = 0; i < 32; i++){
        count += (n>>i & 1);
    }
    return count == 1 && n > 0;
}

Stopover

Answer 24

Kotlin:

fun isPowerOfTwo(n: Int): Boolean {
    return (n > 0) && (n.and(n-1) == 0)
}

or

fun isPowerOfTwo(n: Int): Boolean {
    if (n == 0) return false
    return (n and (n - 1).inv()) == n
}

inv inverts the bits in this value.

---

Note:
log2 solution doesn't work for large numbers, like 536870912 ->

import kotlin.math.truncate
import kotlin.math.log2

fun isPowerOfTwo(n: Int): Boolean {
    return (n > 0) && (log2(n.toDouble())) == truncate(log2(n.toDouble()))
}

Comprador

For unsigned integers, n.countOneBits() == 1 could be used as well. – Dexedrine

Answer 25

In C, I tested the i && !(i & (i - 1) trick and compared it with __builtin_popcount(i), using gcc on Linux, with the -mpopcnt flag to be sure to use the CPU's POPCNT instruction. My test program counted the # of integers in the interval [0, 2^31) that were a power of two.

At first I thought that i && !(i & (i - 1) was 10% faster, even though I verified that POPCNT was used in the disassembly where I used__builtin_popcount.

However, I realized that I had included an if statement, and branch prediction was probably doing better on the bit twiddling version. I removed the if and POPCNT ended up faster, as expected.

Results:

Intel(R) Core(TM) i7-4771 CPU max 3.90GHz

Timing (i & !(i & (i - 1))) trick
30

real    0m13.804s
user    0m13.799s
sys     0m0.000s

Timing POPCNT
30

real    0m11.916s
user    0m11.916s
sys     0m0.000s

AMD Ryzen Threadripper 2950X 16-Core Processor max 3.50GHz

Timing (i && !(i & (i - 1))) trick
30

real    0m13.675s
user    0m13.673s
sys 0m0.000s

Timing POPCNT
30

real    0m13.156s
user    0m13.153s
sys 0m0.000s

Note that here the Intel CPU seems slightly slower than AMD with the bit twiddling, but has a much faster POPCNT; the AMD POPCNT doesn't provide as much of a boost.

popcnt_test.c:

#include "stdio.h"

// Count # of integers that are powers of 2 up to (not including) 2^31;
int main() {
  int n;
  for (int z = 0; z < 20; z++){
      n = 0;
      for (unsigned long i = 0; i < 1<<30; i++) {
       #ifdef USE_POPCNT
        n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
       #else
        n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
       #endif
      }
  }

  printf("%d\n", n);
  return 0;
}

Run tests:

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe

echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe

echo
echo "Timing POPCNT"
time ./test-opt.exe

Tetramethyldiarsine

Comment is 2 up to 2^31 and for loop i = 0; i < 1<<30;, suggest reconciling. Even better: Iterate over all 32-bit values. – Cilium

Thanks -- nice catch. I don't want to rerun this and recompute values at the moment since I don't have as convenient access to the original CPUs, but you're right that the comment (or code) is wrong; fixed. I'm not sure why I stopped early instead of doing all 32 bit values, just being lazy I guess. I like your suggested change: I'd replace for (unsigned long i = 0; i < 1<<30; i++) with for (unsigned long i = 0; i <= 0xFFFFFFFF; i++) { – Tetramethyldiarsine

Note, with 32-bit unsigned long, i <= 0xFFFFFFFF is always true. – Cilium

Answer 26

I see many answers are suggesting to return n && !(n & (n - 1)) but to my experience if the input values are negative it returns false values. I will share another simple approach here since we know a power of two number have only one set bit so simply we will count number of set bit this will take O(log N) time.

while (n > 0) {
    int count = 0;
    n = n & (n - 1);
    count++;
}
return count == 1;

Check this article to count no. of set bits

Tribute

the input is ulong, so it isn't negative – Novation

Answer 27

This is another method to do it as well

package javacore;

import java.util.Scanner;

public class Main_exercise5 {
    public static void main(String[] args) {
        // Local Declaration
        boolean ispoweroftwo = false;
        int n;
        Scanner input = new Scanner (System.in);
        System.out.println("Enter a number");
        n = input.nextInt();
        ispoweroftwo = checkNumber(n);
        System.out.println(ispoweroftwo);
    }
    
    public static boolean checkNumber(int n) {
        // Function declaration
        boolean ispoweroftwo= false;
        // if not divisible by 2, means isnotpoweroftwo
        if(n%2!=0){
            ispoweroftwo=false;
            return ispoweroftwo;
        }
        else {
            for(int power=1; power>0; power=power<<1) {
                if (power==n) {
                    return true;
                }
                else if (power>n) {
                    return false;
                }
            }
        }
        return ispoweroftwo;
    }
}

Gann

Answer 28

This one returns if the number is the power of two up to 64 value ( you can change it inside for loop condition ("6" is for 2^6 is 64);

const isPowerOfTwo = (number) => {
  let result = false;
  for (let i = 1; i <= 6; i++) {
    if (number === Math.pow(2, i)) {
      result = true;
    }
  }
  return result;
};

console.log(isPowerOfTwo(16));
console.log(isPowerOfTwo(10));

Corporeity

Answer 29

There were a number of answers and posted links explaining why the n & (n-1) == 0 works for powers of 2, but I couldn't find any explanation of why it doesn't work for non-powers of 2, so I'm adding this just for completeness.

For n = 1 (2^0 = 1), 1 & 0 = 0, so we are fine.

For odd n > 1, there are at least 2 bits of 1 (left-most and right-most bits). Now n and n-1 will only differ by the right-most bit, so their &-sum will at least have a 1 on the left-most bit, so n & (n-1) != 0:

n:          1xxxx1  for odd n > 1
n-1:        1xxxx0
            ------
n & (n-1):  1xxxx0 != 0

Now for even n that is not a power of 2, we also have at least 2 bits of 1 (left-most and non-right-most). Here, n and n-1 will differ up to the right-most 1 bit, so their &-sum will also have at least a 1 on the left-most bit:

        right-most 1 bit of n
                 v
n:          1xxxx100..00 for even n
n-1:        1xxxx011..11
            ------------
n & (n-1):  1xxxx000..00 != 0

Folacin

Answer 30

I'm assuming 1 is a power of two, which it is, it's 2 to the power of zero

 bool IsPowerOfTwo(ulong testValue)
 {
  ulong bitTest = 1;
  while (bitTest != 0)
  {
    if (bitTest == testValue) return true;
    bitTest = bitTest << 1;
  }

  return false;
}

Novation

Answer 31

private static bool IsPowerOfTwo(ulong x)
{
    var l = Math.Log(x, 2);
    return (l == Math.Floor(l));
}

Derwood

Try that for the number 9223372036854775809. Does it work? I'd think not, because of rounding errors. – Chandos

@Chandos 922337203685477580_9_ doesn't look like a power of 2 to me ;) – Hargrove

@Kirschstein: that number gave him a false positive. – Redoubtable

Kirschstein: It doesn't look like one to me either. It does look like one to the function though... – Chandos