ADVANCED

Count Set Bits (Hamming Weight)

Count the number of set bits (1s) in a 32-bit integer efficiently.

Bit Clearing Loop: n & (n - 1)

Each iteration clears the rightmost set bit. Count the steps until n = 0. [ Kernighan's Method → ]

                        // EXAMPLE 1: n = 7 (00000111)

                        1. 7 & (7-1) → 6 (00000110)

                        2. 6 & (6-1) → 4 (00000100)

                        3. 4 & (4-1) → 0 (00000000)

                        Result: 3 Set Bits

                        // EXAMPLE 2: n = 12 (00001100)

                        1. 12 & (12-1) → 8 (00001000)

                        2. 8 & (8-1) → 0 (00000000)

                        Result: 2 Set Bits

hamming_weight.c

#include <stdint.h>
 
uint32_t countSetBits(uint32_t n) {
 uint32_t count = 0;
 while (n > 0) {
 n &= (n - 1);
 count++;
 }
 return count;
}
 
int main() {
 uint32_t input = 29; // 00011101
 uint32_t setBits =
                        countSetBits(input);
 return 0;
                    
}

Count Set Bits (Hamming Weight)

Bit Clearing Loop: n & (n - 1)

Silicon Applications