This approach involves iterating through each bit of the integer by continuously shifting the bits to the right and checking the least significant bit. Whenever the least significant bit is set, we increment our count. This continues until all bits have been checked.
Time Complexity: O(b) where b is the number of bits in the integer.
Space Complexity: O(1) as no additional space is required.
1#include <stdio.h>
2
3int hammingWeight(unsigned int n) {
4 int count = 0;
5 while (n) {
6 count += n & 1;
7 n >>= 1;
8 }
9 return count;
10}
11
12int main() {
13 printf("%d\n", hammingWeight(11)); // Output: 3
14 printf("%d\n", hammingWeight(128)); // Output: 1
15 printf("%d\n", hammingWeight(2147483645)); // Output: 30
16 return 0;
17}This C code iteratively checks the least significant bit and uses the right shift operation to move the bits of the number. The Hamming weight is calculated by incrementing the count whenever the least significant bit is one. This process continues until all bits in the number have been checked.
This approach leverages the property of bit manipulation where the operation n & (n - 1) results in the number with the lowest set bit turned off. By performing this operation iteratively, the loop proceeds directly to the next set bit, thus reducing the number of iterations required compared to shifting each bit position.
Time Complexity: O(k) where k is the number of set bits.
Space Complexity: O(1) as no extra space is required.
1using System;
2
3public class Program
4{
5 public static int HammingWeight(uint n)
6 {
7 int count = 0;
8 while (n != 0)
9 {
10 n &= (n - 1);
11 count++;
12 }
13 return count;
14 }
15
16 public static void Main()
17 {
18 Console.WriteLine(HammingWeight(11)); // Output: 3
19 Console.WriteLine(HammingWeight(128)); // Output: 1
20 Console.WriteLine(HammingWeight(2147483645)); // Output: 30
21 }
22}This C# method uses the "clear-last-set-bit" strategy to move from one set bit to the next and eliminates it in each iteration until no set bits remain.