> ## Content Index > Fetch the complete content index at: https://www.javahandbook.com/llms.txt > Use this file to discover other available public pages before exploring further. # Hamming Distance - URL: https://www.javahandbook.com/bitmask/hamming-distance-2/ - Published: 2025-08-07T03:26:08.000Z - Updated: 2025-08-07T03:26:08.000Z - Description: Hamming distance talks about two integers where the bit positions where the corresponding bits are different. - Author: Gopi Gorantala - Tags: XOR Operator, #bitmask, #docs In this lesson, we find the number of positions where the bits are different for the given input. ## Introduction In this question, we will find the number of positions at which the corresponding bits are different. ## Problem Statement Given integers `x`, `y` finds the positions where the corresponding bits are different. ```json Input: x = 1, y = 8 Output: 2 Explanation: 1 (0 0 0 1) 8 (1 0 0 0) ↑ ↑ ``` ```json Input: x = 12, y = 15 Output: 2 Explanation: 12 (1 1 0 0) 15 (1 1 1 1) ↑ ↑ ``` ## Solution We solve this using shifting operation and then move to solve it more optimally. ## Bit Shifting This approach is better as it takes `O(1)` time and complexity. We shift the bits to left or right and then check whether the bit is one. ### Algorithm We use the right shift operation, where each bit would have its turn to be shifted to the rightmost position. Once shifted, we use either modulo `%` (i.e., i % 2) or `&` operation (i.e., i & 1). > **Hint:** you can check if a number does not equal 0 by the `^` operator. ### Java ```java class HammingDistance { public static int hammingDistance(int a, int b) { int xor = a ^ b; int distance = 0; while (xor != 0) { if (xor % 2 == 1) { distance += 1; } xor >>= 1; } return distance; } public static void main(String[] args) { int a = 1; int b = 8; System.out.println("Hamming Distance between two integers is " + hammingDistance(a, b)); } } ``` ### Python ```py def HammingDistance(a, b): xor = a ^ b distance = 0 while (xor ^ 0) : if (xor % 2 == 1) : distance += 1 xor >>= 1 return distance a = 1 b = 8 print("Hamming Distance between two integers is", HammingDistance(a, b)) ``` ### JavaScript ```js function HammingDistance(a, b) { let xor = a ^ b; let distance = 0; while (xor ^ 0) { if (xor % 2 === 1) { distance += 1; } xor >>= 1; } return distance; } let a = 1; let b = 8; console.log("Hamming Distance between two integers is", HammingDistance(a, b)); ``` ### C++ ```cpp #include using namespace std; void hammingDistance(int a, int b){ int xorVal = a ^ b; int distance = 0; while(xorVal ^ 0){ if(xorVal % 2 == 1){ distance += 1; } xorVal >>= 1; } cout << "Hamming Distance between two integers is " << distance << endl; } int main() { int a = 1; int b = 8; hammingDistance(a, b); return 0; } ``` ### TypeScript ```ts export const HammingDistance = (a: number, b: number): number => { let xor: number = a ^ b; let distance: number = 0; while (xor ^ 0) { if (xor % 2 === 1) { distance += 1; } xor >>= 1; } return distance; } let a: number= 1; let b: number = 8; console.log("Hamming Distance between two integers is", HammingDistance(a, b)); ``` ### Complexity Analysis **Time complexity:** `O(1)`. For a 32-bit integer, the algorithm would take at most 32 iterations. **Space complexity:** `O(1)`. Memory is constant irrespective of the input. ## Brian Kernighan’s Algorithm In the above approach, we shifted each bit one by one. So, is there a better approach to finding the hamming distance? Yes. ### Algorithm When we do `&` bit operation between number `n` and `(n-1)`, the rightmost bit of one in the original number `n` would be cleared. ```json n = 40 => 00101000 n - 1 = 39 => 00100111 ---------------------------------- (n & (n - 1)) = 32 => 00100000 ---------------------------------- ``` Based on the above idea, we can count the distance in 2 iterations rather than all the shifting iterations we did earlier. Let’s see the code in action. ### Java ```java class HammingDistance { public static int hammingDistance(int a, int b) { int xor = a ^ b; int distance = 0; while (xor != 0) { distance += 1; xor &= ( xor - 1); // equals to `xor = xor & ( xor - 1);` } return distance; } public static void main(String[] args) { int a = 1; int b = 8; System.out.println("Hamming Distance between two integers is " + hammingDistance(a, b)); } } ``` ### Python ```py def HammingDistance(a, b): xor = a ^ b distance = 0 while (xor != 0) : distance += 1 xor &= ( xor - 1) return distance a = 1 b = 8 print("Hamming Distance between two integers is", HammingDistance(a, b)) ``` ### JavaScript ```js function HammingDistance(a, b) { let xor = a ^ b; let distance = 0; while (xor != 0) { distance += 1; xor &= ( xor - 1); // equals to `xor = xor & ( xor - 1);` } return distance; } let a = 1; let b = 8; console.log("Hamming Distance between two integers is", HammingDistance(a, b)); ``` ### C++ ```cpp #include using namespace std; int hammingDistance(int a, int b){ int xorVal = a ^ b; int distance = 0; while (xorVal != 0) { distance += 1; xorVal &= ( xorVal - 1); // equals to `xorVal = xorVal & ( xorVal - 1);` } return distance; } int main() { int a = 1; int b = 8; cout << "Hamming Distance between two integers is " << hammingDistance(a, b); return 0; } ``` ### TypeScript ```ts export const HammingDistance = (a: number, b: number): number => { let xor: number = a ^ b; let distance: number = 0; while (xor != 0) { distance += 1; xor &= ( xor - 1); // equals to `xor = xor & ( xor - 1);` } return distance; } let a: number= 1; let b: number = 8; console.log("Hamming Distance between two integers is", HammingDistance(a, b)); ``` ### Complexity Analysis **Time complexity:** `O(1)`. The input size of the integer is fixed, and we have a constant time complexity. **Space complexity:** `O(1)`. Memory is constant irrespective of the input.