leetcode解题: Hamming Distance (461)

发表于 | 分类于

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

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

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

解法1： O(M), M is the number of bits in difference

这题考察了两个基本操作，一个是XOR的消除操作。XOR两个数得出的数含有所有不一样bit，然后再统计set bit的个数就可以了。如果还记得在统计bit的题目里面的做法，用x & (x - 1)消掉最高位的1直到x变为0为止。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hammingDistance(int x, int y) {
        int temp = x ^ y; 
        return numberOfBits(temp);
    }
    
    int numberOfBits(int x) {
        int count = 0;
        while (x != 0) {
            ++count;
            x = x & (x - 1);
        }
        return count;
    }
};

Java

1