Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
hamming_distance.cpp File Reference

Returns the Hamming distance between two integers. More...

#include <cassert>
#include <iostream>
Include dependency graph for hamming_distance.cpp:

Namespaces

namespace  bit_manipulation
 for IO operations
 
namespace  hamming_distance
 Functions for Hamming distance implementation.
 

Functions

uint64_t bit_manipulation::hamming_distance::bitCount (uint64_t value)
 
uint64_t bit_manipulation::hamming_distance::hamming_distance (uint64_t a, uint64_t b)
 
uint64_t bit_manipulation::hamming_distance::hamming_distance (const std::string &a, const std::string &b)
 
static void test ()
 Function to the test hamming distance.
 
int main ()
 Main function.
 

Detailed Description

Returns the Hamming distance between two integers.

To find hamming distance between two integers, we take their xor, which will have a set bit iff those bits differ in the two numbers. Hence, we return the number of such set bits.

Author
Ravishankar Joshi

Function Documentation

◆ bitCount()

uint64_t bit_manipulation::hamming_distance::bitCount ( uint64_t value)

This function returns the number of set bits in the given number.

Parameters
valuethe number of which we want to count the number of set bits.
Returns
the number of set bits in the given number.
34 {
35 uint64_t count = 0;
36 while (value) { // until all bits are zero
37 if (value & 1) { // check lower bit
38 count++;
39 }
40 value >>= 1; // shift bits, removing lower bit
41 }
42 return count;
43}
Here is the call graph for this function:

◆ hamming_distance() [1/2]

uint64_t bit_manipulation::hamming_distance::hamming_distance ( const std::string & a,
const std::string & b )

This function returns the hamming distance between two strings.

Parameters
athe first string
bthe second string
Returns
the number of characters differing between the two strings.
59 {
60 assert(a.size() == b.size());
61 size_t n = a.size();
62 uint64_t count = 0;
63 for (size_t i = 0; i < n; i++) {
64 count += (b[i] != a[i]);
65 }
66 return count;
67}
T size(T... args)
Here is the call graph for this function:

◆ hamming_distance() [2/2]

uint64_t bit_manipulation::hamming_distance::hamming_distance ( uint64_t a,
uint64_t b )

This function returns the hamming distance between two integers.

Parameters
athe first number
bthe second number
Returns
the number of bits differing between the two integers.
51{ return bitCount(a ^ b); }
uint64_t bitCount(uint64_t value)
Definition hamming_distance.cpp:34
Here is the call graph for this function:

◆ main()

int main ( void )

Main function.

Returns
0 on exit
99 {
100 test(); // execute the tests
101 uint64_t a = 11; // 1011 in binary
102 uint64_t b = 2; // 0010 in binary
103
104 std::cout << "Hamming distance between " << a << " and " << b << " is "
106 << std::endl;
107}
T endl(T... args)
static void test()
Function to the test hamming distance.
Definition hamming_distance.cpp:75
uint64_t hamming_distance(uint64_t a, uint64_t b)
Definition hamming_distance.cpp:51
Here is the call graph for this function:

◆ test()

static void test ( )
static

Function to the test hamming distance.

Returns
void
75 {
76 assert(bit_manipulation::hamming_distance::hamming_distance(11, 2) == 2);
77 assert(bit_manipulation::hamming_distance::hamming_distance(2, 0) == 1);
78 assert(bit_manipulation::hamming_distance::hamming_distance(11, 0) == 3);
79
80 assert(bit_manipulation::hamming_distance::hamming_distance("1101",
81 "1111") == 1);
82 assert(bit_manipulation::hamming_distance::hamming_distance("1111",
83 "1111") == 0);
84 assert(bit_manipulation::hamming_distance::hamming_distance("0000",
85 "1111") == 4);
86
87 assert(bit_manipulation::hamming_distance::hamming_distance("alpha",
88 "alphb") == 1);
89 assert(bit_manipulation::hamming_distance::hamming_distance("abcd",
90 "abcd") == 0);
91 assert(bit_manipulation::hamming_distance::hamming_distance("dcba",
92 "abcd") == 4);
93}