Count the 1 Bits in an Integer

easy bit manipulation

Problem

Given an unsigned integer n, return the number of bits equal to 1 (the Hamming weight). Aim for a loop whose iteration count equals the number of set bits, not the bit width.

Inputn = 0b00000000000000000000000000001011

Output3

Brian Kernighan: n & (n − 1) clears the lowest set bit. Each iteration removes one 1-bit, so the loop runs exactly popcount(n) times.

n (decimal, 0 ≤ n < 2^32)

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

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;
    count++;
  }
  return count;
}

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

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

Time: O(popcount(n)) Space: O(1)