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