Formatted question description: https://leetcode.ca/all/461.html
461. Hamming Distance
Level
Easy
Description
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.
Solution
Compare corresponding bits of x
and y
directly. If the bits are different, add the Hamming distance by 1. Finally, return the Hamming distance.
Java
-
class Solution { public int hammingDistance(int x, int y) { if (x == y) return 0; int distance = 0; while (x > 0 || y > 0) { int xBit = x & 0x1, yBit = y & 0x1; if (xBit != yBit) distance++; x >>>= 1; y >>>= 1; } return distance; } }
-
// OJ: https://leetcode.com/problems/hamming-distance/ // Time: O(1) // Space: O(1) class Solution { public: int hammingDistance(int x, int y) { int ans = 0; for (int z = x ^ y; z; z >>= 1) ans += z & 1; return ans; } };
-
class Solution(object): def hammingDistance(self, x, y): """ :type x: int :type y: int :rtype: int """ x = x ^ y y = 0 while x: y += 1 x = x & (x - 1) return y