461. Hamming Distance

📝 Problem Details

• Title: 461. Hamming Distance
• **Link:**https://leetcode.com/problems/hamming-distance/
• Difficulty: Easy
• Tags/Categories: Bit-Manipulation

💭What Were My Initial Thoughts?

- Hamming Distance: 
	- distance between two integers is the number of positions at which the corresponding bits are different

- XOR can be used to identify differing bits because it returns a 1 for bits that are different and 0 for bits that are the same 

- Counting the number of 1s in the XOR result will give the Hamming distance

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- Compute `x ^ y` (XOR), which highlights the differing bits.
- Initialize `differingBits` to count the number of 1s in the XOR result.
- Use a while loop to iterate through the bits of the XOR result:
    - If the least significant bit is 1 (`xorResult & 1`), increment `differingBits`.
    - Right shift `xorResult` by 1 bit to check the next bit.
- Continue until `xorResult` becomes 0.
- Return `differingBits`, which represents the number of differing bits between x and y.

⌛ Complexity Analysis

Time Complexity: O(32) --> O(1)
	- since we are iterating through the bits, the number of operations is proportional to the number of bits
	- which is at most 32 for a standard integer

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int hammingDistance(int x, int y) {
        int xorResult = x ^ y;
        int differingBits = 0;
 
        // count the number of 1s in XOR result
        while(xorResult) {
            differingBits += xorResult & 1;
            xorResult >>= 1; //right shift by 1 bit
        }
 
        return differingBits;
    }
};