11.2 Number of 1 Bits

11.2.1 Problem Metadata

11.2.2 Description

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).

A set bit refers to a bit in the binary representation of a number that has a value of 1.

Note: In some languages, such as Java, there is no unsigned integer type. In such cases, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.

11.2.3 Examples

Input: n = 11
Output: 3
Explanation: The binary representation of 11 is 00000000000000000000000000001011, which has three set bits.

Input: n = 128
Output: 1
Explanation: The binary representation of 128 is 00000000000000000000000010000000, which has one set bit.

Input: n = 2147483645
Output: 30
Explanation: The binary representation of 2147483645 is 01111111111111111111111111111101, which has thirty set bits.

11.2.4 Constraints

  • \(1 \le n \le 2^{31} - 1\)

11.2.5 Solution 1 - Digit Extraction with Modulo

11.2.5.1 Walkthrough

Extract each bit from right to left using modulo 2 and division. The modulo operation n % 2 gives us the rightmost bit (either 0 or 1), and dividing by 2 (n / 2) effectively shifts the bits right, removing the processed bit. Count each time we encounter a 1.

This approach treats the binary number like a base-2 decimal number, extracting “digits” one at a time.

Example: n = 11 (binary: 1011)

n = 11, result = 0
Iteration 1: residue = 1, n = 5, result = 1
Iteration 2: residue = 1, n = 2, result = 2
Iteration 3: residue = 0, n = 1, result = 2
Iteration 4: residue = 1, n = 0, result = 3
Output: 3

Example: n = 128 (binary: 10000000)

n = 128, result = 0
Iteration 1: residue = 0, n = 64, result = 0
Iteration 2: residue = 0, n = 32, result = 0
Iteration 3: residue = 0, n = 16, result = 0
Iteration 4: residue = 0, n = 8, result = 0
Iteration 5: residue = 0, n = 4, result = 0
Iteration 6: residue = 0, n = 2, result = 0
Iteration 7: residue = 0, n = 1, result = 0
Iteration 8: residue = 1, n = 0, result = 1
Output: 1

11.2.5.2 Analysis

  • Time Complexity: O(log n) or O(32) for 32-bit integers - we process each bit position once
  • Space Complexity: O(1) - only use constant extra space

11.2.5.3 Implementation Steps

  1. Initialize result = 0 to count set bits.
  2. While n is greater than 0:
    • Extract the rightmost bit using n % 2.
    • If the bit is 1, increment result.
    • Remove the rightmost bit by dividing n by 2 (integer division).
  3. Return result.

11.2.5.4 Code - Java

public int hammingWeight(int n) {
    int result = 0;
    int residue = 0;

    while(n > 0) {
        residue = n % 2;
        n = n / 2;

        if(residue == 1)
            result++;
    }

    return result;
}

11.2.6 Solution 2 - Brian Kernighan’s Algorithm

11.2.6.1 Walkthrough

Use the bit manipulation trick n & (n - 1) which removes the rightmost set bit in each iteration. This is more efficient because we only iterate as many times as there are set bits, rather than processing all bit positions.

How n & (n - 1) works: - Subtracting 1 from n flips all bits after the rightmost 1 (including the 1 itself) - ANDing with the original n clears the rightmost 1

Example: n = 11 (binary: 1011)

n = 1011, result = 0
Iteration 1: n & (n-1) = 1011 & 1010 = 1010, result = 1
Iteration 2: n & (n-1) = 1010 & 1001 = 1000, result = 2
Iteration 3: n & (n-1) = 1000 & 0111 = 0000, result = 3
Output: 3

Example: n = 128 (binary: 10000000)

n = 10000000, result = 0
Iteration 1: n & (n-1) = 10000000 & 01111111 = 00000000, result = 1
Output: 1

11.2.6.2 Analysis

  • Time Complexity: O(k) where k is the number of set bits - best case O(1) for sparse numbers, worst case O(32) for numbers with many 1s
  • Space Complexity: O(1)

11.2.6.3 Implementation Steps

  1. Initialize result = 0.
  2. While n is not zero:
    • Apply n &= (n - 1) to remove the rightmost set bit.
    • Increment result.
  3. Return result.

11.2.6.4 Code - Java

public int hammingWeight(int n) {
    int result = 0;
    while(n != 0) {
        n &= (n - 1);  // Remove the rightmost 1 bit
        result++;
    }
    return result;
}