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.
1public class Main {
2 public static int hammingWeight(int n) {
3 int count = 0;
4 while (n != 0) {
5 count += n & 1;
6 n >>>= 1; // Logical shift right
7 }
8 return count;
9 }
10
11 public static void main(String[] args) {
12 System.out.println(hammingWeight(11)); // Output: 3
13 System.out.println(hammingWeight(128)); // Output: 1
14 System.out.println(hammingWeight(2147483645)); // Output: 30
15 }
16}This Java solution involves using bitwise operations to determine the count of set bits in the binary representation of the number. The logical shift operator `>>>=` (unsigned right shift) is used to ensure the correct shifting of bits for signed integers.
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.
1#include <iostream>
2using namespace std;
3
4int hammingWeight(uint32_t n) {
5 int count = 0;
6 while (n) {
7 n &= (n - 1);
8 count++;
9 }
10 return count;
11}
12
13int main() {
14 cout << hammingWeight(11) << endl; // Output: 3
15 cout << hammingWeight(128) << endl; // Output: 1
16 cout << hammingWeight(2147483645) << endl; // Output: 30
17 return 0;
18}This C++ solution optimizes the counting of set bits by iteratively turning off the lowest set bit until the integer becomes zero, counting the number of operations performed.