Number of 1 bits

191.Number of 1 Bits

Bit Manipulation

Math

Problem Statement:

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Example:

Input:

n = 00000000000000000000000000001011

→

Output:

3

The input has three '1' bits

Algorithm:

1. Loop Method: Check each bit with mask
2. Brian Kernighan Method: Clear rightmost set bit
3. Count ones using either approach
4. Handle all 32 bits properly

Complexity:

Loop: O(32) | Brian Kernighan: O(number of 1 bits)

Java Solution:

// Loop method: Check each bit
public int hammingWeightLoop(int n) {
    int count = 0;

    // Check all 32 bits
    for (int i = 0; i < 32; i++) {
        int bit = n & (1 << i);
        if (bit != 0) count++;
    }

    return count;   
}

// Brian Kernighan method: Clear rightmost set bit
public int hammingWeight(int n) {
    int count = 0;
    
    // Clear rightmost set bit until zero
    while (n != 0) {
        n &= (n - 1);  // Clear rightmost 1
        count++;
    }

    return count;   
}

Python Solution:

def hammingWeight(self, n: int) -> int:
    count = 0
    
    # Clear rightmost set bit until zero
    while n:
        n &= (n - 1)  # Clear rightmost 1
        count += 1
        
    return count
    
# Loop method
def hammingWeightLoop(self, n: int) -> int:
    count = 0
    
    # Check all 32 bits
    for i in range(32):
        if n & (1 << i):
            count += 1
            
    return count

C++ Solution:

int hammingWeight(uint32_t n) {
    int count = 0;
    
    // Clear rightmost set bit until zero
    while (n) {
        n &= (n - 1);  // Clear rightmost 1
        count++;
    }
    
    return count;
}

// Loop method
int hammingWeightLoop(uint32_t n) {
    int count = 0;
    
    // Check all 32 bits
    for (int i = 0; i < 32; i++) {
        if (n & (1 << i))
            count++;
    }
    
    return count;
}