Understanding Hamming Weight in Binary Numbers: A PHP Approach

Introduction

The Hamming weight of a binary number refers to the count of the number of 1s (ones) in its binary representation. In this post, we’ll delve into a PHP solution that efficiently computes the Hamming weight of a given integer.

Input: n = 11
Output: 3

Explanation:
The input binary string 1011 has a total of three set bits

Exploring Code

Let’s take a closer look at the PHP class Solution and its method hammingWeight($n):

class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function hammingWeight($n) {
        $count = 0;
        while($n != 0) {
            $n &= ($n - 1); 
            $count++;
        }
        return $count;
    }
}

Explanation

1. Initialization: The function initializes a variable $count to keep track of the number of set bits.
2. Bit Manipulation:
   - Inside the while loop, it repeatedly performs a bitwise AND operation between the current value of $n and $n — 1. This operation effectively clears the least significant bit (the rightmost set bit) of $n.
   - For each iteration, the loop increments $count to count the cleared bit.
   Termination: The loop continues until $n becomes 0, indicating that all bits have been cleared.
3. Return Value: Finally, the function returns the computed Hamming weight stored in $count.

For example:
Initial Value: n = 11 (1011)

Iteration 1:

• Subtract 1 from n: 11 - 1 = 10 (1010)
• Perform a bitwise AND operation between n and n - 1:

  1011 (11)
& 1010 (10)
------
  1010 (10)

• Result after the first iteration: n = 10 (1010)

Iteration 2:

• Subtract 1 from n: 10–1 = 9 (1001)
• Perform a bitwise AND operation between n and n — 1:

  1010 (10)
& 1001 (9)
------
  1000 (8)

• Result after the second iteration: n = 8 (1000)

Iteration 3:

• Subtract 1 from n: 8–1 = 7 (0111)
• Perform a bitwise AND operation between n and n — 1:

  1000 (8)
& 0111 (7)
------
  0000 (0)

• Result after the third iteration: n = 0 (0000)

Termination:

• Since n has become 0, the loop terminates.

In each iteration, the least significant bit that is set to 1 is cleared, and the count of set bits is incremented until n becomes 0.

So, in the case of 11, it takes three iterations to clear all the set bits, resulting in a count of 3 set bits.

Time and Space Complexity

Time Complexity: O(log n), where n is the input integer. This is because the number of iterations in the loop depends on the number of set bits in n.

Space Complexity: O(1),constant space. The code only uses a fixed amount of extra space regardless of the input size.

Conclusion

The provided PHP solution efficiently calculates the Hamming weight of a given integer using bitwise manipulation.

Happy Coding:)