# LeetCode Notes: Hamming Distance

## 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 <= 2
^{31}- 1

## Solution One

**Analysis:**

- Convert decimal to binary
- 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
- 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:

a | b | a XOR b |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

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

a | b | a AND b |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

`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
}
```

## Comments