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 : 

	def Denary2Binary(list):
	'''convert denary integer n to binary string bStr'''
	result = []
	bStr = ''
	for n in list:
	print "n is %s" %n
	if n < 0: raise ValueError, "must be a positive integer"
	if n == 0: return '0'
	while n > 0:
	bStr = str(n % 2) + bStr
	n = n >> 1
	print "bStr is %s" %bStr
	result.append(bStr)
	bStr = ''
	print result
	return result[0],result[1]
	def checkio(data):
	a,b = Denary2Binary(data)
	difference = abs(len(a)-len(b))
	return a,b
	#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"

view raw hamming_distance_hard_way.py hosted with ❤ by GitHub

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 :

	# convert a decimal (denary, base 10) integer to a binary string (base 2)
	# tested with Python24 vegaseat 6/1/2005
	def Denary2Binary(n):
	'''convert denary integer n to binary string bStr'''
	bStr = ''
	if n < 0: raise ValueError, "must be a positive integer"
	if n == 0: return '0'
	while n > 0:
	bStr = str(n % 2) + bStr
	n = n >> 1
	return bStr
	def int2bin(n, count=24):
	"""returns the binary of integer n, using count number of digits"""
	return "".join([str((n >> y) & 1) for y in range(count-1, -1, -1)])
	# this test runs when used as a standalone program, but not as an imported module
	# let's say you save this module as den2bin.py and use it in another program
	# when you import den2bin the __name__ namespace would now be den2bin and the
	# test would be ignored
	if __name__ == '__main__':
	print Denary2Binary(117) # 11111111
	# convert back to test it
	print int(Denary2Binary(255), 2) # 255
	print
	# this version formats the binary
	print int2bin(255, 12) # 000011111111
	# test it
	print int("000011111111", 2) # 255
	print
	# check the exceptions
	print Denary2Binary(0)
	print Denary2Binary(-5) # should give a ValueError

view raw convert_decimal.py hosted with ❤ by GitHub