Number of 1 Bits
Check-and-shift, one bit at a time
time O(32)space O(1)
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.
Details
Animated on: n = 11 (binary 1011) — count the number of set bits.
Problem:Number of 1 BitsEasy
Pattern:Bit Manipulation
Check-and-shift, one bit at a time
step 1 / 6
1
[0]0
[1]1
[2]1
[3]n = 11 = binary 1011. Reading right to left (lowest bit first): bit0=1, bit1=1, bit2=0, bit3=1.
- n=3· arr[3] = 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
Every step in words
Show all 6 steps
- n = 11 = binary 1011. Reading right to left (lowest bit first): bit0=1, bit1=1, bit2=0, bit3=1.
- n & 1 = 1 (lowest bit is 1). count = 1. Shift right: n becomes 101 (binary for 5).
- n & 1 = 1 (lowest bit is 1). count = 2. Shift right: n becomes 10 (binary for 2).
- n & 1 = 0 (lowest bit is 0). count stays 2. Shift right: n becomes 1.
- n & 1 = 1. count = 3. Shift right: n becomes 0, loop ends.
- 11 = 1011 in binary, which has 3 set bits. Return count = 3.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.