Skip to content

Challenge 3: Power of 2

We solve by making use of the & operator in computers. There are many ways to solve this, of which two approaches are simple, and one is a more complex but better solution.

Gopi Gorantala
Gopi Gorantala
3 min read

Table of Contents

In this lesson, we will try to check if the given number is a power of 2. We solve this by writing an efficient algorithm that takes an optimal amount of time.

Introduction

Let’s do another challenging question to check your understanding of Bitwise operators.

Example:

Input: 4
 
Output: True (As 4 is 2^2)
Input: 12
 
Output: False

Problem statement

Write a program to check whether a given number is a power of 2.

Let’s consider a number and find how the AND (&) operator does this.

Input = 64
 
Output: True

Explanation: We solve by making use of the & operator in computers. There are many ways to solve this, of which two approaches are simple, and one is a more complex but better solution.

Assume n is non-negative. Use the & operator to achieve this.

Brute-force/naive approach

Hint: The exciting part of calculating the power of 2 is that they have a set-bit count equal to one.

Algorithm

  • Read the input value.
  • Repeatedly divide input with 2.
    • if n not equal to 1 and if it is odd, we will return false.
    • else true.

Here is what our algorithm will look like:

Solutions

Java

class IsPowerOf2 {
    private static boolean helper(int n) {
        if (n == 0) {
            return false;
        }

        while (n != 1) {
            if (n % 2 != 0) {
                return false;
            }
            n >>= 1;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(helper(6));
        System.out.println(helper(8));
    }
}

Python

def IsPowerOf2(n):
    if n == 0:
        return False
    while n != 1:
        if n %2 !=0:
            return False
        n >>= 1
    return True

print(IsPowerOf2(6))
print(IsPowerOf2(8))

JavaScript

const IsPowerOf2 = number => {

    function helper (n) {
        if(n === 0) {
            return false;
        }

        while (n !== 1) {
            if(n % 2 !== 0) {
                return false;
            }
            n >>= 1;
        }
        return true;
    }

    return helper (number);
}

console.log (IsPowerOf2 (6));
console.log (IsPowerOf2 (8));

C++

#include <iostream>

using namespace std;

bool helper(int n) {
    if (n == 0) {
        return false;
    }
    while (n != 1) {
        if (n % 2 != 0) {
            return false;
        }
        n >>= 1;
    }
    return true;
}

int main() {
    cout << helper(6) << endl;
    cout << helper(8) << endl;
    return 0;
}

TypeScript

export const IsPowerOf2 = (n: number): boolean => {
    function helper(value: number): boolean {
        if (value === 0) {
            return false;
        }

        while (value !== 1) {
            if (value % 2 !== 0) {
                return false;
            }
            value >>= 1;
        }
        return true;
    }

    return helper(n);
}

console.log(IsPowerOf2(6));
console.log(IsPowerOf2(8));

Complexity analysis

Time complexity

This takes log(n) complexity. We can do better in constant time using Brian Kernighan’s algorithm.

Space complexity

The space complexity is O(1). No additional space is allocated.

Coding exercise

Now, try to optimize the above solution/algorithm. There is a better way to solve this problem.

This problem is designed for your practice, so try to solve it yourself first. If you get stuck, you can always refer to the solution in the next lesson. Good luck!

Hint: Learn about "Brian Kernighan’s algorithm", because in next solution review, we are about to solve this with his approach.

First, look at these code snippets below and think of a solution.

// Java
// TODO: finish the challenge or check next lesson for solution
class Solution{
    public static boolean isPow2(int n){
        // Write - Your - Code- Here

        return false; // change this, return true/false based on inputs
    }
}
# Python
# TODO: finish the challenge or check next lesson for solution
def Solution(n):
	# Write - Your - Code- Here
    
	return False # change this, return True/False based on inputs
// JavaScript
// TODO: finish the challenge or check next lesson for solution
const isPow2 = n => {
    // Write - Your - Code- Here
    
    return false; // change this, return true/false based on inputs
}
// C++
// TODO: finish the challenge or check next lesson for solution
#include <iostream>
#include <string>
using namespace std;

bool isPowerOfTwo(int n) {
   // Write - Your - Code- Here

    return false; // change this, return true/false based on inputs
}
// TypeScript
// TODO: finish the challenge or check next lesson for solution
export const isPow2 = (n: number): boolean => {
    // Write - Your - Code- Here
    
    return false; // change this, return true/false based on inputs
}

The solution will be explained in the next lesson.

Bit Manipulation

Gopi Gorantala Twitter

Gopi has been a Full Stack(Java+React) since 2016. He worked in Europe, and India, from startups to tech giants. He has a strong engineering professional with a Bachelor's in Satellite Communications.

Comments


Related Posts

Members Public

Solution Review: Get the First Set Bit Position Using the Right Shift

In the kth bit set/unset problem, we first write the algorithm, then some pseudocode, and then implement the solution.

Members Public

Challenge 1: Get the First Set Bit Position Using the Right Shift

This problem is similar to the last lesson we discussed. If you need a clue, return to the previous lesson to further your understanding.

Members Public

Check If Kth Bit Is Set/Unset Using Right Shift

In the kth bit set/unset problem, we need to write a program that checks whether the kth bit of a number is 1 or 0.