Number of 1 bits

Problem Statement

LeetCode-191: Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Input: 11
Output: 3
Explanation: The input binary string '1011' has a total of three set bits.

Input: 128
Output: 1
Explanation: The input binary string '10000000' has a total of one set bit.

Approach

There are two primary approaches to solve this problem:

1. Bit Manipulation: We can use the bitwise AND operator to check if the least significant bit of the number is set or not. If it is set, we increment the count of set bits. We then right shift the number by one bit to check the next bit. We continue this process until the number becomes zero.

2. Brian Kernighan’s Algorithm: This algorithm is based on the observation that for any number n, n & (n-1) will unset the least significant bit that is set in n. We can use this property to count the number of set bits in a number. We discussed the same in another counting-bits post as well.

Implementation

Let’s implement the first approach using bit manipulation.

public int hammingWeight(int n) {
    int count = 0;
    while(n != 0){
        // if the least significant bit is set
        // increment the count
        if((n & 1) != 0){
            count++;
        }
        // right shift the number by one bit
        n= n >> 1;
    }
    return count;
}

Let’s implement the second approach using Brian Kernighan’s Algorithm.

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

Complexity Analysis

The first approach has a fixed time complexity of $O(32) \approx O(1)$ since we are iterating over all the bits of the number.

The second approach has a time complexity of $O(k)$, where $k$ is the number of set bits in the number $n$. In the worst case (all bits set to 1), $k$ can be $O(\log \ n)$, where $n$ is the input number.