Count set bits in an integer

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}