The ultimate guide to bit manipulation for coding interviews. Developed by FAANG engineers, practice with real-world interview questions, and get interview-ready in just a few hours.

This course teaches bit manipulation, a powerful technique to enhance algorithmic and problem-solving skills. It is a critical topic for those preparing for coding interviews for top tech companies, startups and industry leaders. Competitive programmers can take full advantage of this course by running most of the bit-related problems in O(1) complexity.

The course will begin by educating you about the number system and its representation, decimal and binary, followed by the six bitwise operators: AND, OR, NOT, XOR, and bit-shifting (left, right).

You will receive ample practical experience working through practice problems to improve your comprehension.

Upon completing this course, you will be able to solve problems with greater efficiency and speed.

Grokking Bit Manipulation for Coding Interviews

# Solution review
We saw an algorithm to solve this problem in the previous lesson. Let's see how to solve this in a more efficient way using Briann's Algorithm.

## Brian Kernighan's algorithm

This is a faster execution than the previous naive approach.

In this approach, we count only the set bits. So,
* If a number has 2 set bits, then the while loop runs two times.

* If a number has 4 set bits, then the while loop runs four times.

For example, let us consider the example `n = 125` and calculate using this algorithm.

class CountSetBit {
    private static int helper(int n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int number = 125;
        System.out.println("SetBit Count is : " + helper(number));
    }
}


Java

def CountSetBits(n):
    count=0
    while n > 0:
        n &= (n - 1)
        count+=1
    return count

number=125
print('SetBit Count is : ', CountSetBits(number))

Python

#include <iostream>
using namespace std;

int helper(int n){
    int count = 0;
    
    while (n > 0){
        n &= (n - 1);
        count++;
    }

    return count;
}

int main() {
    int number = 125;
    cout << "SetBit count is : " << helper(number);
}

const CountSetBits = (n) => {
    let count = 0;
    
    while (n > 0) {
        n &= (n - 1);
        count++;
    }

    return count;
}

console.log ('SetBit Count is', CountSetBits (125));


JavaScript

export const CountSetBits = (n: number): number => {
    let count: number = 0;

    while (n > 0) {
        n &= (n - 1);
        count++;
    }

    return count;
}

console.log('SetBit Count is', CountSetBits(125));

TypeScript

```
         n  = 40    => 00000000 00000000 00000000 00101000
      n - 1 = 39    => 00000000 00000000 00000000 00100111
-----------------------------------------------------------
(n & (n - 1)) = 32  => 00000000 00000000 00000000 00100000   
-----------------------------------------------------------    
```

Now n is 32, so we can calculate this to:

```
         n  = 32    => 00000000 00000000 00000000 00100000
      n - 1 = 31    => 00000000 00000000 00000000 00011111
-----------------------------------------------------------
(n & (n - 1)) = 0   => 00000000 00000000 00000000 00000000   
-----------------------------------------------------------
```

## Time and space complexities

**Time complexity: O(Set Bit count) / O(1) in simple terms**

The time taken is proportional to set bits in binary representation.

So, time taken is O(SetBit Count).

The run time depends on the number of set 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(32)$ or $O(1)$.

**Space complexity: O(1) extra space**

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

This review provides a detailed analysis to solve the count set bits

Getting Started

Number Systems, Bitwise, and Binary

Bitwise AND

Bitwise OR

Bitwise NOT

Bitwise XOR

Bit Shifting - Left, Right

Bitwise LeftShift Problems

Bitwise RightShift Problems

Final Thoughts

Solution Review: Count Set Bits

Solution review

Brian Kernighan’s algorithm

Explanation