LeetCode Notes: Hamming Distance

#leetcode

Question

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

Example 1:

Input: x = 1, y = 4

Output: 2

Explanation:

1   (0  0  0  1)

4   (0  1  0  0)

        ▲     ▲

The above triangle arrows point to positions where the corresponding bits are different.

Example 2:

Input: x = 3, y = 1

Output: 1

Constraints:

  • 0 <= x, y <= 231 - 1

Solution One

Analysis:

  1. Convert decimal to binary
  2. For shorter binary digits, add 0 on the left to make a string of the same length as the second digit, which is convenient for comparison, because the 0 on the left will not affect the original value
  3. Traverse the binary string and count the number of different characters

Code:

/**
  * @param {number} x
  * @param {number} y
  * @return {number}
  */
var hammingDistance = function(x, y) {
    
     // Convert decimal to binary
     let xToBinary = x.toString(2)
     let yToBinary = y.toString(2)

     // Get the length
     const xLength = xToBinary.length
     const yLength = yToBinary.length

     // Take the longest of the two
     const maxLength = Math.max(xLength,yLength)
    
     // Add 0 to the left of the shorter number to make a string of the same length as the second number
     if(xLength < maxLength){
         xToBinary = '0'.repeat(maxLength-xLength) + xToBinary
     }else if(yLength <maxLength){
         yToBinary = '0'.repeat(maxLength-yLength) + yToBinary
     }

     // Traverse the string and count the number of different characters
     let count = 0
     for(let i = 0; i < maxLength; i++){
         if(xToBinary[i] !== yToBinary[i]){
             count++
         }
     }

     return count

};

Solution Two

Analysis:

1. Use bitwise XOR ^ to get the number of different numbers in x and y.

Let's review the characteristics of bitwise XOR, the same is 0, and the difference is 1, as follows:

aba XOR b
000
011
101
110

2. The number of 1s in the binary digits obtained by the statistics is the result value. We use the bitwise AND operator &.

Let's review the characteristics of bitwise AND, both numbers are 1 and the result is 1, otherwise it is 0, as follows:

aba AND b
000
010
100
111

num & (num-1) can convert the rightmost 1 of the binary number of num into 0

The principle of conversion is as follows:

  • num = 3

The rightmost 1 of 3 is the penultimate number

3      (1  1)
 
2      (1  0)
 
3 & 2  (1  0)
 
           ▲
  • num = 10

The rightmost 1 of 10 is the second-to-last number

10      (1  0  1  0)
 
9       (1  0  0  1)
 
10 & 9  (1  0  0  0)
 
               ▲

Copy the following code to the console to see the print result:

console.log((3).toString(2)) // Output:11
console.log((2).toString(2)) // Output:10
console.log((3 & 2).toString(2)) // Output:10(The 1 on the far right is converted to 0)

console.log((10).toString(2)) // Output:1010
console.log((9).toString(2)) // Output:1001
console.log((10 & 9).toString(2)) // Output:1000(The 1 on the far right is converted to 0)

Every conversion, count once, and the final result is the number of 1s in the num binary number.

Note that num is always a decimal number, and the conversion effect will be performed in binary representation.

Code:

/**
  * @param {number} x
  * @param {number} y
  * @return {number}
  */
var hammingDistance = function(x, y) {
    
     // Bitwise XOR, making all different numbers count as 1
     let num = x ^ y

     // Count the number of 1s in binary
     let count = 0
     while(num){
         // Convert the rightmost 1 of the binary number to 0
         num = num & (num-1)
         // 1 for every conversion, count once
         count++
     }
     return count

};

Or we can extract a general method to specifically count the number of ones in binary.

/**
  * @param {number} x
  * @param {number} y
  * @return {number}
  */
var hammingDistance = function(x, y) {
    
     // Bitwise XOR, making all different numbers count as 1
     let num = x ^ y

     // Count the number of 1s in binary
     return countBinaryOne(num)

};

/**
Count the number of 1s in binary
* @param {number} num
* @return {number}
*/
var countBinaryOne = function(num){
    let count = 0
    while(num){
        // Convert the rightmost 1 of the binary number to 0
        num = num & (num-1)
        // 1 for every conversion, count once
        count++
    }
    return count
}

Solution Three

Analysis:

1. This is an upgrade to the second solution. We still use the bitwise XOR ^ to convert the numbers first, and count the number of 1, and we will transform the function of counting the number of 1s in the binary system.

2. Execute num & 1, a bitwise AND of any number and number 1, you can judge whether the rightmost binary number is 1, if it is 1, it will count, if it is not 1, it will not be counted.

The principle of judgment is as follows:

  • num = 3

The rightmost binary digit of 3 is 1

3      (1  1)
 
1      (0  1)
 
3 & 1  (0  1)
 
           ▲
  • num = 10

The rightmost binary digit of 10 is 0

10      (1  0  1  0)
 
1       (0  0  0  1)
 
10 & 1  (0  0  0  0)
 
                  ▲

Copy the following code to the console to see the print result:

console.log((3).toString(2)) // Output:11
console.log((1).toString(2)) // Output:1
console.log((3 & 1).toString(2)) // Output:1(The rightmost of 3 is 1)

console.log((10).toString(2)) // Output:1010
console.log((1).toString(2)) // Output:1010
console.log((10 & 1).toString(2)) // Output:0(The rightmost of 10 is 0)

3. After counting the rightmost digits, we use the right shift operator >> to shift the digits to the right by one bit, and remove the rightmost binary digit

Note: Right shift assignment x >>= 1 is shorthand for the result of right shift operation x = x >> 1

Perform right shift operator:

  • num = 3
3       (1  1)
 
         ▲
 
3 >> 1  (0  1)
 
            ▲
  • num = 10
10       (1  0  1  0)
 
          ▲  ▲  ▲
 
10 >> 1  (0  1  0  1)
 
             ▲  ▲  ▲

Copy the following code to the console to see the print result:

console.log((3).toString(2)) // Output:11
console.log((3 >> 1).toString(2)) // Output:1

console.log((10).toString(2)) // Output:1010
console.log((10 >> 1).toString(2)) // Output:101

4. Then continue to cycle to the rightmost number to judge and count until the number becomes 0 and stop

Code:

/**
  * @param {number} x
  * @param {number} y
  * @return {number}
  */
var hammingDistance = function(x, y) {
    
     // Bitwise XOR, making all different numbers count as 1
     let num = x ^ y

     // Count the number of 1s in binary
     return countBinaryOne(num)

};

/**
    Count the number of 1s in binary
  * @param {number} num
  * @return {number}
  */
var countBinaryOne = function(num){
     let count = 0
     while(num){
         // Determine if the rightmost number is 1, if the result is 1, add 1, and if it is 0, add 0
         count += num & 1
         // The rightmost number has been counted, move right to eliminate it
         num >>= 1
     }
     return count
}

Reference

Comments