Skip to content

Hamming Distance

Hamming distance talks about two integers where the bit positions where the corresponding bits are different.

Gopi Gorantala
Gopi Gorantala
3 min read

In this lesson, we find the number of positions where the bits are different for the given input.

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 move to solve it more optimally.

Bit Shifting

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

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).

Hint: you can check if a number does not equal 0 by the ^ operator.

Java

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));
    }
}

Python

def HammingDistance(a, b):
   xor = a ^ b
   distance = 0

   while (xor ^ 0) :
    if (xor % 2 == 1) :
        distance += 1
    
    xor >>= 1
    
   return distance

a = 1
b = 8
print("Hamming Distance between two integers is", HammingDistance(a, b))

JavaScript

function HammingDistance(a, b) {
  let xor = a ^ b;
  let distance = 0;

  while (xor ^ 0) {
    if (xor % 2 === 1) {
        distance += 1;
    }
    xor >>= 1;
  }

  return distance;
}

let a = 1;
let b = 8;
console.log("Hamming Distance between two integers is", HammingDistance(a, b));

C++

#include <iostream>
using namespace std;

void hammingDistance(int a, int b){
  int xorVal = a ^ b;
  int distance = 0;

  while(xorVal ^ 0){
    if(xorVal % 2 == 1){
      distance += 1;
    }
    xorVal >>= 1;
  }
  cout << "Hamming Distance between two integers is " << distance << endl;
}

int main() {
  int a = 1;
  int b = 8;
  hammingDistance(a, b);
  return 0;
}

TypeScript

export const HammingDistance = (a: number, b: number): number => {
  let xor: number = a ^ b;
  let distance: number = 0;

  while (xor ^ 0) {
    if (xor % 2 === 1) {
        distance += 1;
    }
    xor >>= 1;
  }

  return distance;
}

let a: number= 1;
let b: number = 8;
console.log("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 to 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.

Java

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));
  }
}

Python

def HammingDistance(a, b):
   xor = a ^ b
   distance = 0

   while (xor != 0) :
     distance += 1
     xor &= ( xor - 1)
  
   return distance

a = 1
b = 8
print("Hamming Distance between two integers is", HammingDistance(a, b))

JavaScript

function HammingDistance(a, b) {
  let xor = a ^ b;
  let distance = 0;

  while (xor != 0) {
    distance += 1;
    xor &= ( xor - 1); // equals to `xor = xor & ( xor - 1);`
  }

  return distance;
}

let a = 1;
let b = 8;
console.log("Hamming Distance between two integers is", HammingDistance(a, b));

C++

#include <iostream>
using namespace std;

int hammingDistance(int a, int b){
  int xorVal = a ^ b;
  int distance = 0;

  while (xorVal != 0) {
    distance += 1;
    xorVal &= ( xorVal - 1); // equals to `xorVal = xorVal & ( xorVal - 1);`
  }

  return distance;
}

int main() {
  int a = 1;
  int b = 8;
  cout << "Hamming Distance between two integers is " << hammingDistance(a, b);
  return 0;
}

TypeScript

export const HammingDistance = (a: number, b: number): number => {
  let xor: number = a ^ b;
  let distance: number = 0;

  while (xor != 0) {
    distance += 1;
    xor &= ( xor - 1); // equals to `xor = xor & ( xor - 1);`
  }

  return distance;
}

let a: number= 1;
let b: number = 8;
console.log("Hamming Distance between two integers is", HammingDistance(a, b));

Complexity Analysis

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

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

Coding Interview QuestionsData Structures and AlgorithmsBit Manipulation

Gopi Gorantala Twitter

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Comments


Related Posts

Members Public

Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Leetcode 217: Contains Duplicate
Members Public

Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Leetcode 121: Best Time To Buy and Sell Stock
Members Public

Bit Manipulation Course Overview

Overview In this course, you will learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize your algorithmic and problem-solving skills. This is one of the most important/critical topics when someone starts preparing for coding interviews for FAANG companies. To kick things