hamming_distance.cpp File Reference

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

#include <cassert>
#include <cstdint>
#include <iostream>

Include dependency graph for hamming_distance.cpp:

Go to the source code of this file.

Namespaces
namespace	bit_manipulation
	for assert
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

Definition in file hamming_distance.cpp.

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

value

the number of which we want to count the number of set bits.

Returns

the number of set bits in the given number.

Definition at line 35 of file hamming_distance.cpp.

                                  {
    uint64_t count = 0;
    while (value) {       // until all bits are zero
        if (value & 1) {  // check lower bit
            count++;
        }
        value >>= 1;  // shift bits, removing lower bit
    }
    return count;
}

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

a	the first string
b	the second string

Returns

the number of characters differing between the two strings.

Definition at line 60 of file hamming_distance.cpp.

                                                                  {
    assert(a.size() == b.size());
    size_t n = a.size();
    uint64_t count = 0;
    for (size_t i = 0; i < n; i++) {
        count += (b[i] != a[i]);
    }
    return count;
}

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

a	the first number
b	the second number

Returns

the number of bits differing between the two integers.

Definition at line 52 of file hamming_distance.cpp.

{ return bitCount(a ^ b); }

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 100 of file hamming_distance.cpp.

           {
    test();           // execute the tests
    uint64_t a = 11;  // 1011 in binary
    uint64_t b = 2;   // 0010 in binary
 
    std::cout << "Hamming distance between " << a << " and " << b << " is "
              << bit_manipulation::hamming_distance::hamming_distance(a, b)
              << std::endl;
}

test()

static void test ( )

static

Function to the test hamming distance.

Returns

void

Definition at line 76 of file hamming_distance.cpp.

                   {
    assert(bit_manipulation::hamming_distance::hamming_distance(11, 2) == 2);
    assert(bit_manipulation::hamming_distance::hamming_distance(2, 0) == 1);
    assert(bit_manipulation::hamming_distance::hamming_distance(11, 0) == 3);
 
    assert(bit_manipulation::hamming_distance::hamming_distance("1101",
                                                                "1111") == 1);
    assert(bit_manipulation::hamming_distance::hamming_distance("1111",
                                                                "1111") == 0);
    assert(bit_manipulation::hamming_distance::hamming_distance("0000",
                                                                "1111") == 4);
 
    assert(bit_manipulation::hamming_distance::hamming_distance("alpha",
                                                                "alphb") == 1);
    assert(bit_manipulation::hamming_distance::hamming_distance("abcd",
                                                                "abcd") == 0);
    assert(bit_manipulation::hamming_distance::hamming_distance("dcba",
                                                                "abcd") == 4);
}