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.
1def hammingWeight(n: int) -> int:
2 count = 0
3 while n:
4 count += n & 1
5 n >>= 1
6 return count
7
8# Testing
9def main():
10 print(hammingWeight(11)) # Output: 3
11 print(hammingWeight(128)) # Output: 1
12 print(hammingWeight(2147483645)) # Output: 30
13
14main()The Python function performs a similar iteration and bit-checking process, incrementing the count whenever the least significant bit is 1. The right shift operator effectively shifts the bits to the right until the number becomes zero.
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.
1function hammingWeight(n) {
2 let count = 0;
3 while (n !== 0) {
4 n &= n - 1;
5 count++;
6 }
7 return count;
8}
9
10console.log(hammingWeight(11)); // Output: 3
11console.log(hammingWeight(128)); // Output: 1
12console.log(hammingWeight(2147483645)); // Output: 30This JavaScript function efficiently counts the number of set bits by applying the operation n & (n - 1), which removes the lowest set bit, repeating until the integer becomes zero.