Pattern visualizer
Number of 1 Bits
n & 1 isolates just the lowest bit (0 or 1), because AND-ing with 1 zeroes out every other bit. Check that bit, count it if it's 1, then shift n right by one to bring the next bit into that lowest position — repeat until n is 0 and every bit has been inspected exactly once. Animated on: n = 11 (binary 1011) — count the number of set bits..
Check-and-shift, one bit at a time
time O(32)space O(1)step 1 / 6
1
[0]0
[1]1
[2]1
[3]line 2
n = 11 = binary 1011. Reading right to left (lowest bit first): bit0=1, bit1=1, bit2=0, bit3=1.
Pseudocode
1FUNCTION hammingWeight(n):2 count = 03 WHILE n > 0:4 IF the lowest bit of n is 1:5 add 1 to count6 shift n right by one bit7 RETURN count
← / → step · space play · Home restart