Skip to content

Solution Review: Power of 2

Let's solve this using brain kernighan's algorithm. This is optimized to O(1) time and space.

Gopi Gorantala
Gopi Gorantala
3 min read

Table of Contents

Let's see how we use Brain Kernighan's algorithm to achieve this.

Solution review: Brian Kernighan’s algorithm

We saw an algorithm to solve this problem in the previous lesson. Let’s see how to solve this more efficiently using Briann’s Algorithm.

In this approach, we count the set bits. If a number is the power of 2, we know that only one set bit is present in its Binary representation.

In binary, we go from right to left with powers of 2.

For example:

20, 21, 22, 23, 24, and so on...

Algorithm

Before we talk about algorithmic steps, you should review the table data and slider shown below the table.

  • if (n & (n - 1) == 0), return true
  • else, false

Let’s visualize the values in the table below:

n n (in binary) (n - 1) (n - 1) in binary n & (n - 1) (n & (n - 1) == 0)
2 0010 (2 - 1) = 1 0001 (2 & 1) = 0 true
6 0110 (6 - 1) = 5 0101 (6 & 5) = 4 false
8 1000 (8 - 1) = 7 0111 (8 & 7) = 0 true
10 1010 (10 - 1) = 9 1001 (10 & 9) = 8 false

Let’s see a couple of examples:

        n   = 4    => 00000000 00000000 00000000 00000100
      n - 1 = 3    => 00000000 00000000 00000000 00000011
-----------------------------------------------------------
(n & (n - 1)) = 0  => 00000000 00000000 00000000 00000000   
-----------------------------------------------------------

( n & (n - 1)), here this becomes 0, which is true. Hence, the number 4 is a power of 2.

        n   = 6    => 00000000 00000000 00000000 00000110
      n - 1 = 5    => 00000000 00000000 00000000 00000101
-----------------------------------------------------------
(n & (n - 1)) = 4  => 00000000 00000000 00000000 00000100   
-----------------------------------------------------------

( n & (n - 1)) is 4, which is not equal to 0. Hence, the number 6 is not a power of 2.

Solution

Here is the reasoning behind this solution.

Java

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

    /**
     * Return boolean(even/odd) for the given number.
     *
     * @param n
     * @return
     */
    private static boolean helper(int n) {
        if (n == 0) {
            return false;
        }
        return (n & (n - 1)) == 0;
    }
}

We can further simplify this code into a single line shown below.

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

    /**
     * Return boolean(even/odd) for the given number.
     *
     * @param n
     * @return
     */
    private static boolean helper(int n) {
        return n != 0 && (n & (n - 1)) == 0;
    }
}

Python

def helper(n):
    if n == 0:
        return False
    return (n & (n - 1) == 0)

print(helper(6))
print(helper(8))

We can further simplify this code into a single line shown below.

def IsPowerOf2(n):
    return n != 0 and (n & (n - 1)==0)

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

JavaScript

/**
 * Return boolean(even/odd) for the given number.
 *
 * @param {number} number
 * @return {boolean}
 */
const IsPowerOf2 = number => {

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

    return helper (number);
}

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

We can further simplify this code into a single line shown below.

/**
 * Return boolean(even/odd) for the given number.
 *
 * @param {number} number
 * @return {boolean}
 */
const IsPowerOf2 = n => {
    return n !== 0 && (n & (n - 1)) === 0;
}

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

C++

#include <iostream>

using namespace std;

bool helper(int n) {
    if (n == 0) {
        return false;//0 represents as false and 1 represents as true.
    }
    return (n & (n - 1)) == 0;
}

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

We can further simplify this code into a single line shown below.

#include <iostream>

using namespace std;

bool helper(int n) {
  return n != 0 && (n & (n - 1)) == 0;
}

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;
        }
        return (value & (value - 1)) === 0;
    }

    return helper(n);
}

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

We can further simplify this code into a single line shown below.

const IsPowerOf2 = (n: number): boolean => {
    return n !== 0 && (n & (n - 1)) === 0;
}

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

Complexity analysis

Time complexity: O(1)

The run time depends on the number of 1-bits in n. In the worst case, all bits in n are 1-bits. In the case of a 32-bit integer, the run time is O(1).

Space complexity: O(1)

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

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.