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
- Initialization: The function initializes a variable $count to keep track of the number of set bits.
- 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. - 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
andn - 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 become0
, 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:)