Given a positive integer n, write a function that returns the number of set bits it has (also known as Hamming weight).

Example 1:

• Input: n = 11
• Output: 3
• Explanation: 11 in binary is 1011 (3 set bits)

Constraints:

• 1 <= n <= 2^31 - 1

n & (n - 1) clears the lowest set bit.

Brian Kernighan’s Bit Counting Algorithm

graph TD
    A["Input Integer / Bits"] --> B["Apply Bitwise Operation (AND / XOR / Shift)"]
    B --> C{"Check Bit Condition"}
    C -- "Condition Met" --> D["Update Bit Count / Result"]
    C -- "Continue" --> E["Shift Bits (>>> 1 or & n-1)"]
    E --> B
    D --> F["Return Final Result"]

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

• Time Complexity: O(32)
• Space Complexity: O(1)
• Explanation: Shift bits right 32 times.

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

• Time Complexity: O(set bits)
• Space Complexity: O(1)
• Explanation: Clears lowest set bit in each iteration.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

n & (n - 1) removes the least significant 1-bit in O(k) operations.

1. Use n & (n - 1) to clear bits one by one.

👉 Solve this problem interactively in the DSA Lab