Bit Manipulation: Power of Two

Bit manipulation is one of the advanced topics in terms of problem-solving and interview preparation. This is also one of my favorite topics. At first, bit manipulation might seem a little bit intimidating; however, with some practice, it’s very easy to apply this technique in problem-solving.

In this article, we are gonna discuss a problem called the Power of two where bit manipulation is the best way to solve this. Let’s first take a look at the problem statement:

Given an integer N, return true if the number is a power of two; otherwise, return false.

Well, let’s first talk about how the power of two looks like in binary. The binary form of the power of two looks like this pattern: 100….0.

2^0 = 1 
2^1 = 2 = b(10)  
2^2 = 4 = b(100)
2^3 = 8 = b(1000)

So basically we can generate the power of two with number 1 by left shifting it n times. So for example, if we wanna get 2⁸ we need to simply shift 1 on the left 8 times.

Now we need to determine if the given number is actually a power of two. So we can see, for a number to be a power of two the MSB(Most Significant Bit; the leftmost bit) will be 1 followed by zero or more zeroes. That means there will be only one set bit(1) in that number. Therefore, if a number has only 1 set bit that would be a power of two! Here’s the code snippet:

public boolean isPowerOfTwo(int n) {
        int count = 0;
        while(n>0){
            count+= (n & 1); // counting…