How to calculate the sum of Hamming distance in PHP

The Hamming distance of two integers refers to the number of different binary corresponding bits of the two numbers. Today, the editor will introduce the method of calculating the sum of Hamming distances in PHP. You can refer to it if you need it.

The Hamming distance of two integers refers to the number of different corresponding bits in the binary digits of these two numbers.

Calculate the sum of Hamming distances between any two numbers in an array.

Example:

输入: 4, 14, 2
输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

The range of elements in the array is from 0 to 10^9. The length of the array cannot exceed 10^4.

Problem-solving ideas 1

Enumerate the number of pairwise combinations and then accumulate the Hamming distance. This is the simplest and most straightforward solution.

The result is that it will time out when there is a large amount of data, and the number of factorials is too many.

Code

class Solution {
    /** 
    * @param Integer[] $nums 
    * @return Integer 
    */
    function totalHammingDistance($nums) {
        $count = count($nums);
        $sum = 0;
        for ($i = 0; $i < $count - 1; $i++) {
            for ($j = $i+1; $j < $count; $j++) 
            {
                $sum += $this->hm($nums[$i], $nums[$j]);
            }
        }
        return $sum;
    }
    // 汉明距离方法
    function hm($x, $y)
    {
        return substr_count(decbin($x ^ $y), &#39;1&#39;);
    }}

Problem-solving idea 2 - Vertical calculation

We often analyze the problem like this: the simplest case-> General , complex situations. Previously we were: traversing all possible pairwise combinations.

Now let's look at it from another angle: if int has only 1 bit -> int has 32 bits.

First of all, if int has only 1 bit, that is, the elements in the array nums have only two situations, 0 or 1. At this time, the steps to find the sum of Hamming distances are as follows:

First divide the array into Two groups, one group with all 0 digits, and one group with all 1 digits. Combine the two groups of numbers in pairs, record one as a and the other as b. If a and b both come from the group of 0, or both come from the group of 1, this There will be no Hamming distance generated. But if one of a and b comes from the 0 group, and the other one comes from the 1 group, Hamming distance will be generated. Assume that the number of elements in the nums array is n, and the number of 0 elements is k, then the number of 1 elements The number is n-k, then the sum of Hamming distances that can be generated in the previous step is k*(n-k)k*(n-k), which is the sum of Hamming distances when int has only 1 digit.

If the number of digits in int is Expanding from 1 bit to 32 bits, then each bit is traversed, and then the sum of Hamming distances at this bit is found, and accumulated together. This can reduce the algorithm complexity from $O(N^2)$ To $O(32\times N)$, it is $O(N)$.

You can look at the following example:

十进制       二进制
4:        0 1 0 0
14:        1 1 1 0
2:        0 0 1 0
1:        0 0 0 1

Look at the last column first. There are three 0s and one 1. Then the Hamming distance between them is 3, that is, 1 and the other three 0s. The respective distances are accumulated, and then when looking at the third column, the accumulated Hamming distance is 4, because each 1 will produce two Hamming distances with two 0s. Similarly, the second column is also 4, and the first column is 3. The sum of the Hamming distances of the pairwise combinations of each column is the sum of the number of 0s and the number of 1s in each column. Adding up the sum of the Hamming distances of each column is the distance between the two elements of the array nums required by the question. Sum of Hamming distances.

Code

class Solution {

    /** 
    * @param Integer[] $nums 
    * @return Integer 
    */
    function totalHammingDistance($nums) {
        $count = count($nums);
        $sum = 0;
        for($i = 0; $i < 32; $i++)
        {
            $tmpCount = 0; 
            
            for($j = 0; $j < $count; $j++)
            {
                $tmpCount += ($nums[$j] >> $i) & 1;
            }
            
            $sum += $tmpCount * ($count - $tmpCount);
        }
         
        return $sum;
    }
}

Recommended learning: php video tutorial

The above is the detailed content of How to calculate the sum of Hamming distance in PHP. For more information, please follow other related articles on the PHP Chinese website!