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 01: Input: 4
 
Output: True (As 4 is 2^2) Example 02: Input: 12
 
Output: False Problem Statement Write a program to check if a given number is a power of 2 or not. Let’s consider a number and find how the AND operator does this. Input = 64
 
Output: True Explanation We solve this by making use of the operator in computers. There are many ways to solve this, of which two approaches are simple, and one of them is a more complex but better solution. & Assume is non-negative. We use the operator to achieve this. n & Solution: Brute-Force/Naive Approach The exciting part of calculating the power of 2 is that they have a set-bit count equal to one. Hint: Algorithm Read the input value. Repeatedly divide input with . 2 if is not equal to and if it is , we will return . n 1 odd false else . true Here is what our algorithm will look like: Code export const IsEven = (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(IsEven(6));
console.log(IsEven(8)); Complexity Analysis Time complexity: O(logn) This takes complexity. We can do better in constant time using the . log(n) Brian Kernighan’s algorithm Space complexity: O(1) The space complexity is . It allocated no additional space. O(1) Coding Exercise First, inspect the code snippets above and think of a solution. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the solution provided in the solution section. Good luck! export const isPow2 = (n: number): boolean => {
    // Write - Your - Code- Here
    
    return false; // change this, return true/false based on inputs
} If you've got the answer, great! If not, it's normal, practice similar problems and you'll get a good hold of bit manipulation tricks. I will explain the solution below. Let's see how we make use of Brian Kernighan's algorithm to achieve this. Solution Review: Brian Kernighan’s Algorithm This is considered faster than the previous naive approach. 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: 2^0, 2^1, 2^2, 2^3, 2^4, and so on. Algorithm Before we talk about algorithmic steps, review the tabular form of steps that depict the algorithm. If , return . (n & (n - 1) == 0) True else, . False Let’s visualize the values in the table below: 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   
----------------------------------------------------------- , here this becomes , which is . Hence, the number is a power of 2. (n&(n - 1)) 0 true 4 n   = 6    => 00000000 00000000 00000000 00000110
      n - 1 = 5    => 00000000 00000000 00000000 00000101
-----------------------------------------------------------
(n & (n - 1)) = 4   => 00000000 00000000 00000000 00000100   
----------------------------------------------------------- is , which is not equal to . Hence, the number is not a power of 2. (n&(n - 1)) 4 0 6 Let us look at the optimized approach. Code Here is the reasoning behind this solution. export const IsEven = (n: number): boolean => {
    function helper(value: number): boolean {
        if (value === 0) {
            return false;
        }
        return (value & (value - 1)) === 0;
    }

    return helper(n);
}

console.log(IsEven(6));
console.log(IsEven(8)); We can further simplify this code into a single line shown below. const IsEven = (n: number): boolean => {
    return n !== 0 && (n & (n - 1)) === 0;
}

console.log (IsEven (6));
console.log (IsEven (8)); Complexity Analysis Time complexity: O(1) The run time depends on the number of in . In the worst case, all bits in are . With a integer, the runtime is . 1-bits n n 1-bits 32-bit O(1) Space complexity: O(1) The space complexity is . It allocated no additional space. O(1) Extras If you are interested in mastering bit tricks, I've got a course that more than 100k+ programmers loved. In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can optimize your algorithmic and problem-solving skills. The course has a simple explanation with sketches, detailed step-by-step drawings, and various ways to solve it using bitwise operators. These bit-tricks could help in competitive programming and coding interviews in running algorithms, mostly in time. O(1) This is one of the most important/critical topics when someone prepares for coding interviews for FAANG(Facebook, Amazon, Apple, Netflix, and Google) companies. To kick things off, you’ll start by learning about the number system and how it’s represented. Then you’ll move on to learn about the six different bitwise operators: AND, OR, NOT, XOR, and bit shifting. Throughout, you will get tons of hands-on experience working through practice problems to help sharpen your understanding. By the time you’ve completed this course, you will solve problems faster with greater efficiency!! 🤩 Link to my course: . Master Bit Manipulation for Coding Interviews Co-published . here

Amazon

Apple

Facebook

Google

Netflix

A Deeper Look into Method References in Java

A Closer Look into Different Programming Styles and Paradigms

ggorantala.dev

My Portfolio

Buy My Course: Grokking Bit Manipulation For Coding Interviews.

Buy Me a Coffee

10% off educative.io

The Complete Junior to Senior Web Developer Roadmap (2022)

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Functional Programming

Too Long; Didn't Read

Is a Given Number the Power of 2? 

Is a Given Number the Power of 2?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Closer Look into Different Programming Styles and Paradigms

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

A Closer Look into Different Programming Styles and Paradigms

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps