461. Hamming Distance

Problem statement

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.

Example 1

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

Example 2

Input: x = 3, y = 1
Output: 1

Constraints

0 <= x, y <= 2^31.

Solution: Using bitwise operator XOR

You could use bit operator ^ (XOR) to get the bit positions where x and y are different. Then use bit operator & (AND) at each position to count them.

Code

#include <iostream>
int hammingDistance(int x, int y) {
    int z = x ^ y;
    int count = 0;
    while (z) {
        count += z & 1;
        z = z >> 1;
    }
    return count;
}
int main() {
    std::cout << hammingDistance(1,4) << std::endl;
    std::cout << hammingDistance(1,3) << std::endl;
}

Output:
2
1

Complexity

Runtime: O(1).
Extra space: O(1).

References

https://leetcode.com/problems/hamming-distance/

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.

461. Hamming Distance

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Constraints

Solution: Using bitwise operator XOR

Code

Complexity

References

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Constraints

Solution: Using bitwise operator XOR

Code

Complexity

References