~ read.

The Hamming distance task solution

I was going through new interesting tasks on http://www.checkio.org/ and faced with bytes task about Hamming distance calculation. Here's some theory about this : 
The Hamming distance between two binary integers is the number of bit positions that differs (http://en.wikipedia.org/wiki/Hamming_distance). For example: 
117 = 0 1 1 1 0 1 0 1 17 = 0 0 0 1 0 0 0 1 H = 0+1+1+0+0+1+0+0 = 3 
And the task was : 

Given two positive integers in decimal form. You should calculate the Hamming distance between these two numbers in binary form.

I don't like tasks with bytes because i don't understand them fully:) So, i started googling and playing around with different solutions. In the end i got my code running and completing the task as it was required : 

And then i got access to other people solutions. Well, it was very surprising and exciting to see this nice, clean and short solution for my problem:) 
def checkio(data):
a, b = data
return str(bin(a^b)).count('1')

#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([117, 17]) == 3, "First example"
assert checkio([1, 2]) == 2, "Second example"
assert checkio([16, 15]) == 5, "Third example"

Which, we all have to admit, is cool and looks really good. For the one who just start studying python here's some short description of how this cool algorithm works : According to python docs :
Bitwise operator works on bits and perform bit by bit operation. Assume if a = 60; and b = 13; Now in binary format they will be as follows: a = 0011 1100 b = 0000 1101 ----------------- a&b = 0000 1100 a|b = 0011 1101 a^b = 0011 0001 ~a  = 1100 0011
So,
  1. bin() - converts ints into bytes
  2. a^b - Binary XOR Operator copies the bit if it is set in one operand but not both
  3. .count("1") - counts how many 1 in result
Nice and easy:)
P.S. while i was googling about this convertation from int into bytes and back, i found useful python script which i used for my method :
comments powered by Disqus
comments powered by Disqus