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 < 2³¹.

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

• Java
• C++
• Python

• 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
  
  

All Problems

All Solutions