Bit Manipulation - Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, return the Hamming distance between them.

Input: x = 1, y = 4
Output: 2
Explanation: 1 (0001) XOR 4 (0100) = 0101. Two bits differ.

Input: x = 3, y = 1
Output: 1
Explanation: 3 (011) XOR 1 (001) = 010. One bit differs.

XOR of x and y produces a number where each 1-bit represents a position where x and y differ. Count the number of 1-bits in the XOR result using the n & (n-1) trick or Java's built-in Integer.bitCount.

Compute xor = x ^ y. Each set bit in xor indicates a differing position.
Count the 1-bits in xor using Integer.bitCount or a manual loop.
Return the count.

class Solution { public int hammingDistance(int x, int y) { int xor = x ^ y; int count = 0; while (xor != 0) { xor &= (xor - 1); // clear lowest set bit count++; } return count; } }

Complexity Analysis:

Time complexity: O(1) — bounded by the number of set bits (at most 32).
Space complexity: O(1) — constant extra space.