Create hamming-distance.py

kamyu104 · web-flow · commit 9e44778e09ec · 2016-12-20T12:46:01.000+08:00
diff --git a/Python/hamming-distance.py b/Python/hamming-distance.py
@@ -0,0 +1,37 @@
+# Time:  O(1)
+# Space: O(1)
+
+# The Hamming distance between two integers is the number of positions
+# at which the corresponding bits are different.
+#
+# Given two integers x and y, calculate the Hamming distance.
+#
+# Note:
+# 0 &le; x, y < 231.
+#
+# Example:
+#
+# Input: x = 1, y = 4
+#
+# Output: 2
+#
+# Explanation:
+# 1   (0 0 0 1)
+# 4   (0 1 0 0)
+#       &uarr;   &uarr;
+#
+# The above arrows point to positions where the corresponding bits are different.
+
+class Solution(object):
+    def hammingDistance(self, x, y):
+        """
+        :type x: int
+        :type y: int
+        :rtype: int
+        """
+        distance = 0
+        z = x^y
+        while z:
+            distance += 1
+            z &= z-1
+        return distance
