Count set bits in an integer
Problem
Return the number of 1 bits in the binary form of a non-negative integer (its Hamming weight).
Example 1
Input: n = 11 (1011) Output: 3
Also asked as: number of 1 bits · count total set bits
Test cases
Case 1
Input: 11 Expected: 3
Case 2
Input: 128 Expected: 1
Case 3
Input: 0 Expected: 0
View solutionHide solution2 approaches
1. Kernighan’s trick
Time O(set bits)Space O(1)
`n & (n - 1)` clears the lowest set bit; count how many times you can do it.
function countSetBits(n) { let count = 0; while (n) { n &= n - 1; count++; } return count;}2. Shift and mask
Time O(32)Space O(1)
Check the last bit, shift right, repeat 32 times.
function countSetBits(n) { let count = 0; for (let i = 0; i < 32; i++) count += (n >>> i) & 1; return count;}