Skip to main content

Hamming distance of two integers

The Hamming distance is a metric used to measure the difference between two strings of equal length. In computer science, it is often applied to integers as well. In the context of integers, the Hamming distance is the number of positions at which the corresponding bits differ in the binary representation of the two integers. For example, the Hamming distance between 4 (binary: 100) and 7 (binary: 111) is 1, as they differ in the rightmost bit. This concept has various applications, including error detection and correction, DNA sequence analysis, and network coding.

Problem Statement

Given two integers, A and B, we are required to find their Hamming distance. The goal is to determine the number of positions at which the binary representations of A and B have different bits.

Example

Consider two integers, A = 15 (binary: 1111) and B = 10 (binary: 1010). The Hamming distance between A and B can be calculated as follows: 

Step 1: XOR the two integers: A ^ B
		1111 (A)
	XOR 1010 (B)
	----------
		0101

Step 2: Count the number of '1' bits in the result from Step 1.
		Result: 0101 -> 2 '1' bits

Thus, the Hamming distance between A and B is 2.

Pseudocode


    1. Read integers A and B as input.
    2. Set a variable 'num' to A XOR B.
    3. Set a variable 'count' to 0.
    4. While 'num' is greater than 0, do the following:
         a. Increment 'count' by 1.
         b. Update 'num' to 'num' AND (num - 1).
    5. Print the value of 'count' as the Hamming distance.

Algorithm Explanation

The algorithm begins by calculating the XOR of integers A and B and storing the result in the variable 'num'. XOR operation returns a number with '1' bits at positions where the corresponding bits of A and B differ. Next, the algorithm counts the number of '1' bits in 'num' using a technique called Brian Kernighan's Algorithm. In each iteration, the algorithm flips the rightmost '1' bit in 'num' to '0' by performing 'num = num & (num - 1)', and increments the 'count' by 1. This process continues until 'num' becomes zero, ensuring that all '1' bits are counted.

Code Solution

// C Program 
// Hamming distance of two integers
#include <stdio.h>

// Find hamming distance
void hammingDistance(int a, int b)
{
	// Display given number
	printf("\n Number A : %d", a);
	printf("\n Number B : %d", b);
	int num = a ^ b;
	int count = 0;
	// Count active bits
	while (num > 0)
	{
		count++;
		num = num & (num - 1);
	}
	// Display hamming distance
	printf("\n Hamming Distance : %d\n", count);
}
int main(int argc, char const *argv[])
{
	// Test Cases
	// 15 [1111], 
	// 10 [1010]
	hammingDistance(15, 10);
	// 123 [1111011], 
	//  37 [ 100101]
	hammingDistance(123, 37);
	// 18 [10010], 
	// 18 [10010]
	hammingDistance(18, 18);
	return 0;
}

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0
/*
  Java Program 
  Hamming distance of two integers
*/
public class Distance
{
	// Find hamming distance
	public void hammingDistance(int a, int b)
	{
		// Display given number
		System.out.print("\n Number A : " + a);
		System.out.print("\n Number B : " + b);
		int num = a ^ b;
		int count = 0;
		// Count active bits
		while (num > 0)
		{
			count++;
			num = num & (num - 1);
		}
		// Display hamming distance
		System.out.print("\n Hamming Distance : " + count + "\n");
	}
	public static void main(String[] args)
	{
		Distance task = new Distance();
		// Test Cases
		// 15 [1111], 
		// 10 [1010]
		task.hammingDistance(15, 10);
		// 123 [1111011], 
		//  37 [ 100101]
		task.hammingDistance(123, 37);
		// 18 [10010], 
		// 18 [10010]
		task.hammingDistance(18, 18);
	}
}

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Hamming distance of two integers
*/
class Distance
{
	public:
		// Find hamming distance
		void hammingDistance(int a, int b)
		{
			// Display given number
			cout << "\n Number A : " << a;
			cout << "\n Number B : " << b;
			int num = a ^ b;
			int count = 0;
			// Count active bits
			while (num > 0)
			{
				count++;
				num = num &(num - 1);
			}
			// Display hamming distance
			cout << "\n Hamming Distance : " << count << "\n";
		}
};
int main()
{
	Distance task = Distance();
	// Test Cases
	// 15 [1111]
	// 10 [1010]
	task.hammingDistance(15, 10);
	// 123 [1111011]
	//  37 [0100101]
	task.hammingDistance(123, 37);
	// 18 [10010]
	// 18 [10010]
	task.hammingDistance(18, 18);
	return 0;
}

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0
// Include namespace system
using System;
/*
  C# Program 
  Hamming distance of two integers
*/
public class Distance
{
	// Find hamming distance
	public void hammingDistance(int a, int b)
	{
		// Display given number
		Console.Write("\n Number A : " + a);
		Console.Write("\n Number B : " + b);
		int num = a ^ b;
		int count = 0;
		// Count active bits
		while (num > 0)
		{
			count++;
			num = num & (num - 1);
		}
		// Display hamming distance
		Console.Write("\n Hamming Distance : " + count + "\n");
	}
	public static void Main(String[] args)
	{
		Distance task = new Distance();
		// Test Cases
		// 15 [1111]
		// 10 [1010]
		task.hammingDistance(15, 10);
		// 123 [1111011]
		//  37 [0100101]
		task.hammingDistance(123, 37);
		// 18 [10010]
		// 18 [10010]
		task.hammingDistance(18, 18);
	}
}

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0
<?php
/*
  Php Program 
  Hamming distance of two integers
*/
class Distance
{
	// Find hamming distance
	public	function hammingDistance($a, $b)
	{
		// Display given number
		echo "\n Number A : ". $a;
		echo "\n Number B : ". $b;
		$num = $a ^ $b;
		$count = 0;
		// Count active bits
		while ($num > 0)
		{
			$count++;
			$num = $num & ($num - 1);
		}
		// Display hamming distance
		echo "\n Hamming Distance : ". $count ."\n";
	}
}

function main()
{
	$task = new Distance();
	// Test Cases
	// 15 [1111]
	// 10 [1010]
	$task->hammingDistance(15, 10);
	// 123 [1111011]
	//  37 [0100101]
	$task->hammingDistance(123, 37);
	// 18 [10010]
	// 18 [10010]
	$task->hammingDistance(18, 18);
}
main();

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0
/*
  Node Js Program 
  Hamming distance of two integers
*/
class Distance
{
	// Find hamming distance
	hammingDistance(a, b)
	{
		// Display given number
		process.stdout.write("\n Number A : " + a);
		process.stdout.write("\n Number B : " + b);
		var num = a ^ b;
		var count = 0;
		// Count active bits
		while (num > 0)
		{
			count++;
			num = num & (num - 1);
		}
		// Display hamming distance
		process.stdout.write("\n Hamming Distance : " + count + "\n");
	}
}

function main()
{
	var task = new Distance();
	// Test Cases
	// 15 [1111]
	// 10 [1010]
	task.hammingDistance(15, 10);
	// 123 [1111011]
	//  37 [0100101]
	task.hammingDistance(123, 37);
	// 18 [10010]
	// 18 [10010]
	task.hammingDistance(18, 18);
}
main();

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0
#   Python 3 Program 
#   Hamming distance of two integers

class Distance :
	#  Find hamming distance
	def hammingDistance(self, a, b) :
		#  Display given number
		print("\n Number A : ", a, end = "")
		print("\n Number B : ", b, end = "")
		num = a ^ b
		count = 0
		#  Count active bits
		while (num > 0) :
			count += 1
			num = num & (num - 1)
		
		#  Display hamming distance
		print("\n Hamming Distance : ", count )
	

def main() :
	task = Distance()
	#  Test Cases
	#  15 [1111]
	#  10 [1010]
	task.hammingDistance(15, 10)
	#  123 [1111011]
	#   37 [0100101]
	task.hammingDistance(123, 37)
	#  18 [10010]
	#  18 [10010]
	task.hammingDistance(18, 18)

if __name__ == "__main__": main()

Output

 Number A :  15
 Number B :  10
 Hamming Distance :  2

 Number A :  123
 Number B :  37
 Hamming Distance :  5

 Number A :  18
 Number B :  18
 Hamming Distance :  0
#   Ruby Program 
#   Hamming distance of two integers

class Distance 
	#  Find hamming distance
	def hammingDistance(a, b) 
		#  Display given number
		print("\n Number A : ", a)
		print("\n Number B : ", b)
		num = a ^ b
		count = 0
		#  Count active bits
		while (num > 0) 
			count += 1
			num = num & (num - 1)
		end

		#  Display hamming distance
		print("\n Hamming Distance : ", count ,"\n")
	end

end

def main() 
	task = Distance.new()
	#  Test Cases
	#  15 [1111]
	#  10 [1010]
	task.hammingDistance(15, 10)
	#  123 [1111011]
	#   37 [0100101]
	task.hammingDistance(123, 37)
	#  18 [10010]
	#  18 [10010]
	task.hammingDistance(18, 18)
end

main()

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0

/*
  Scala Program 
  Hamming distance of two integers
*/
class Distance
{
	// Find hamming distance
	def hammingDistance(a: Int, b: Int): Unit = {
		// Display given number
		print("\n Number A : " + a);
		print("\n Number B : " + b);
		var num: Int = a ^ b;
		var count: Int = 0;
		// Count active bits
		while (num > 0)
		{
			count += 1;
			num = num & (num - 1);
		}
		// Display hamming distance
		print("\n Hamming Distance : " + count + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Distance = new Distance();
		// Test Cases
		// 15 [1111]
		// 10 [1010]
		task.hammingDistance(15, 10);
		// 123 [1111011]
		//  37 [0100101]
		task.hammingDistance(123, 37);
		// 18 [10010]
		// 18 [10010]
		task.hammingDistance(18, 18);
	}
}

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0
/*
  Swift 4 Program 
  Hamming distance of two integers
*/
class Distance
{
	// Find hamming distance
	func hammingDistance(_ a: Int, _ b: Int)
	{
		// Display given number
		print("\n Number A : ", a, terminator: "");
		print("\n Number B : ", b, terminator: "");
		var num: Int = a ^ b;
		var count: Int = 0;
		// Count active bits
		while (num > 0)
		{
			count += 1;
			num = num & (num - 1);
		}
		// Display hamming distance
		print("\n Hamming Distance : ", count );
	}
}
func main()
{
	let task: Distance = Distance();
	// Test Cases
	// 15 [1111]
	// 10 [1010]
	task.hammingDistance(15, 10);
	// 123 [1111011]
	//  37 [0100101]
	task.hammingDistance(123, 37);
	// 18 [10010]
	// 18 [10010]
	task.hammingDistance(18, 18);
}
main();

Output

 Number A :  15
 Number B :  10
 Hamming Distance :  2

 Number A :  123
 Number B :  37
 Hamming Distance :  5

 Number A :  18
 Number B :  18
 Hamming Distance :  0
/*
  Kotlin Program 
  Hamming distance of two integers
*/
class Distance
{
	// Find hamming distance
	fun hammingDistance(a: Int, b: Int): Unit
	{
		// Display given number
		print("\n Number A : " + a);
		print("\n Number B : " + b);
		var num: Int = a xor b;
		var count: Int = 0;
		// Count active bits
		while (num > 0)
		{
			count += 1;
			num = num and (num - 1);
		}
		// Display hamming distance
		print("\n Hamming Distance : " + count + "\n");
	}
}
fun main(args: Array <String> ): Unit
{
	var task: Distance = Distance();
	// Test Cases
	// 15 [1111]
	// 10 [1010]
	task.hammingDistance(15, 10);
	// 123 [1111011]
	//  37 [0100101]
	task.hammingDistance(123, 37);
	// 18 [10010]
	// 18 [10010]
	task.hammingDistance(18, 18);
}

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0
// Rust Program 
// Hamming distance of two integers
fn main()
{
	// Test Cases
	// 15 [1111], 
	// 10 [1010]
	hamming_distance(15, 10);
	// 123 [1111011], 
	//  37 [ 100101]
	hamming_distance(123, 37);
	// 18 [10010], 
	// 18 [10010]
	hamming_distance(18, 18);
}
fn hamming_distance(a: i32, b: i32)
{
	// Display given number
	print!("\n Number A : {}", a);
	print!("\n Number B : {}", b);
	let mut num: i32 = a ^ b;
	let mut count: i32 = 0;
	// Count active bits
	while num > 0
	{
		count += 1;
		num = num & (num - 1);
	}
	// Display hamming distance
	print!("\n Hamming Distance : {}\n", count);
}

Output

 Number A : 15
 Number B : 10
 Hamming Distance : 2

 Number A : 123
 Number B : 37
 Hamming Distance : 5

 Number A : 18
 Number B : 18
 Hamming Distance : 0

Resultant Output Explanation

The algorithm is applied to three test cases:

  • A = 15, B = 10: The Hamming distance is 2, as shown in the example above.
  • A = 123, B = 37: The Hamming distance is 5, which means they differ in five bit positions.
  • A = 18, B = 18: Both numbers are identical (same binary representation), resulting in a Hamming distance of 0.

Time Complexity

The time complexity of the algorithm is O(log(max(A, B))), where max(A, B) is the larger of the two input integers. The reason is that the algorithm counts the '1' bits in the binary representation of 'num', which has at most log(max(A, B)) '1' bits. The 'while' loop executes for each '1' bit, and the number of '1' bits is proportional to the binary representation's length.

Finally

The Hamming distance is a useful metric to determine the dissimilarity between two integers or strings. The algorithm to calculate the Hamming distance for two integers using XOR and Brian Kernighan's Algorithm provides an efficient solution. It counts the differing bits in the binary representation of the two integers and provides an accurate Hamming distance. Its time complexity ensures that it can handle large integers efficiently.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment