How can we decide that an integer is power of 2 by using bit manipulation?

Question

For example if the given number n = 16 If it is power of 2 then the output should be true else false, i want the answer by using bit manipulation.

If the number is a power of two, then there is only one 1 bit in the entire number. Also, `n & (n-1)` will be 0. — Tim Roberts, Sep 15 '22 at 05:12
@TimRoberts can you please elaborate by taking an example it would help me a lot !! Thank you for your comment — Kushal_Hemanth, Sep 15 '22 at 05:14
@Kushal_Hemanth try running the code I share. Also, read the explanation on GeeksforGeeks. Hope this helps — Shisui Otsutsuki, Sep 15 '22 at 05:15
@ShisuiOtsutsuki i have udneestood that thanks for you help !! — Kushal_Hemanth, Sep 15 '22 at 05:16
@Kushal_Hemanth if the answers help you try to mark them ok because that helps other people as well. Thanks! — Shisui Otsutsuki, Sep 15 '22 at 05:21
If using C++, you might want to check out [std::has_single_bit](https://en.cppreference.com/w/cpp/numeric/has_single_bit) — BoP, Sep 15 '22 at 08:51
@BoP, good utility function, but works only with compilers supporting C++ 20. — kiner_shah, Sep 15 '22 at 10:23

kiner_shah · Accepted Answer · 2022-09-15T10:19:41.963

3

The solution mentioned by @TimRoberts is the most simple way of using bit manipulation.

Just check if (n & (n - 1) == 0). Why does this work?

Assume n = 8 (1000 in base 2), then n - 1 = 7 (0111 in base 2). If you do a bitwise AND of these two, you get 0. This is true for n equal to any power of 2.

So you function should simply be:

bool is_power_of_2(unsigned long n)
{
    return n != 0 && (n & (n - 1)) == 0;
}

edited Sep 15 '22 at 10:19

answered Sep 15 '22 at 06:10

kiner_shah

3,939
7
23
37

1

Note that this incorrectly reports 0 to be a power of two. You should account for that, for example like `return n && !(n & (n - 1))`. You can also find this solution in [this](https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2) wonderful resource for bit manipulation hacks by Sean Eron Anderson. – Jakob Stark Sep 15 '22 at 07:23
1

@JakobStark, thanks for pointing this out. Made the edits. – kiner_shah Sep 15 '22 at 10:19

Shisui Otsutsuki · Answer 2 · 2022-09-15T05:19:35.930

2

Does this work? Source GeeksforGeeks:

def isPowerOfTwo(n):
    cnt = 0
    while n > 0:
        if n & 1 == 1:
            cnt = cnt + 1
        n = n >> 1
 
    if cnt == 1:
        return 1
    return 0

# Driver code
if __name__ == "__main__":
 
    # Function call
    if(isPowerOfTwo(31)):
        print('Yes')
    else:
        print('No')
 
    if(isPowerOfTwo(64)):
        print('Yes')
    else:
        print('No')

Explanation:

All powers of 2 have only 1-bit set in them

Examples: 2 --> 10, 4 --> 100, 8 --> 1000, 16 --> 10000, so on

edited Sep 15 '22 at 05:19

answered Sep 15 '22 at 05:13

Shisui Otsutsuki

296
1
9

Your function will return `1` when `n == 1`. I don't think `1` is considered a power of 2. – selbie Sep 15 '22 at 05:15
you can use if and else if it reurns 1 then yes otherwise no – Shisui Otsutsuki Sep 15 '22 at 05:17
3

nevermind, I had a brain fart. – selbie Sep 15 '22 at 05:27
1

Or, better, just use [std::has_single_bit](https://en.cppreference.com/w/cpp/numeric/has_single_bit). – Jesper Juhl Sep 15 '22 at 09:40
@JesperJuhl, that would work only if the compiler supports C++ 20. But yes, it's a good utility function. – kiner_shah Sep 15 '22 at 10:21

How can we decide that an integer is power of 2 by using bit manipulation?

2 Answers2