Understanding Hamming Weight in Binary Numbers: A PHP Approach

Athira Radhakrishnan
2 min readMar 25, 2024

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:)

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

Athira Radhakrishnan
Athira Radhakrishnan

Written by Athira Radhakrishnan

Systems Engineer | PHP | SQL | Magento | Aspiring Cybersecurity Student | Professionally active since 2021 | GitHub : https://github.com/AthiraBR

No responses yet

Write a response