Search⌘ K
AI Features
Home
Courses
Grokking Bit Manipulation for Coding Interviews

Hamming Distance

Explore how to find the Hamming Distance between two integers by identifying differing bits. Understand bit shifting and Brian Kernighan’s algorithm to solve the problem efficiently with constant time and space complexity.

We'll cover the following...

Introduction

In this question, we will find the number of positions at which the corresponding bits are different.

Problem Statement

Given integers x, y finds the positions where the corresponding bits are different.

Input: x = 1, y = 8
Output: 2
Explanation:
1   (0 0 0 1)
8   (1 0 0 0)
     ↑     ↑

Input: x = 12, y = 15
Output: 2
Explanation:
12   (1 1 0 0)
15   (1 1 1 1)
          ↑ ↑

Solution

We solve this using shifting operation and then we move to solve it in a more optimal way.

Bit Shifting

This approach is better as it takes O(1) time complexity. We shift the bits to left or right and then check if the bit is one or not.

Algorithm

We use the right shift operation, where each bit would have its turn to be shifted to the rightmost position.

Once shifted we use either modulo % (i.e., i % 2) or & operation (i.e., i & 1).

Code

Hint: you can check if a number does not equal 0 by the ^ operator. We use this in the below approach in JS, C++, and TypeScript code snippets.

class HammingDistance {
    public static int hammingDistance(int a, int b) {
        int xor = a ^ b;
        int distance = 0;
        while (xor != 0) {
            if (xor % 2 == 1) {
                distance += 1;
            }
            xor >>= 1;
        }
        return distance;
    }
    public static void main(String[] args) {
        int a = 1;
        int b = 8;
        System.out.println("Hamming Distance between two integers is " + hammingDistance(a, b));
    }
}

Complexity Analysis

Time complexity: O(1). For a 32 bit integer, the algorithm would take at most 32 iterations.

Space complexity: O(1). Memory is constant irrespective of the input.

Brian Kernighan’s Algorithm

In the above approach, we shifted each bit one by one. So, is there a better approach in finding the hamming distance? Yes.

Algorithm

When we do & bit operation between number n and (n-1), the rightmost bit of one in the original number n would be cleared.

      n       = 40  => 00101000
    n - 1     = 39  => 00100111
----------------------------------
(n & (n - 1)) = 32  => 00100000   
----------------------------------

Based on the above idea, we can count the distance in 2 iterations rather than all the shifting iterations we did earlier. Let’s see the code in action.

Code

class HammingDistance {
  public static int hammingDistance(int a, int b) {
    int xor = a ^ b;
    int distance = 0;
    while (xor != 0) {
      distance += 1;
      xor &= ( xor - 1); // equals to `xor = xor & ( xor - 1);`
    }
    return distance;
  }
  public static void main(String[] args) {
    int a = 1;
    int b = 8;
    System.out.println("Hamming Distance between two integers is " + hammingDistance(a, b));
  }
}

Complexity Analysis

Time complexity: O(1). The input size of the integer is fixed, we have a constant time complexity.

Space complexity: O(1). Memory is constant irrespective of the input.