< Back




461. Hamming Distance

Fun little bit manipluation problem. We're asked to find the Hamming Distance of two numbers, the
number of bits that are different between the two. We use XOR to find the bits that aren't the same
between the two numbers, and then we shift the result of that XOR operation right until it equals
zero. During each shift, we check to see if the rightmost bit is on and we add it to the result if
it is - this a bit that was different between the two numbers. Finally, we return the Hamming
Distance.

The solution is as follows:


  class Solution:
      def hammingDistance(self, x: int, y: int) -> int:
          ans, xor = 0, x ^ y

          while xor:
              ans += 1 & xor
              xor >>= 1

          return ans


_ Time Complexity:

  O(1) - Even though we shift right until the result of the XOR operation is 0, there are at most
  32 bits in a Python integer, so we execute this operation in constant time.

_ Space Complexity:

  O(1) - We maintain constant space to store our scalar values.