Hamming Distance Solution (Java w/Bitwise Operators)


  • 0
    R

    We can use bitwise operators to keep shifting the bits to the right and extracting the right most bits.

    Given the integers x and y, we can extract the right most bits by using the bitwise AND operator:

    int x = 1; // binary: 0001
    int y = 4; // binary: 1000
    
    // Extract the right most bits:
    int xr = x & 0b1; // 1
    int yr = y & 0b1; // 0
    
    // Shift the bits down:
    x = x >> 1; // binary: 0000
    y = y >> 1; // binary: 0100
    
    // Use the XOR operator to determine if the bits are different:
    boolean different = (x ^ y) == 1;
    
    // Repeat the process
    

    Solution:

    class Solution {
        public int hammingDistance(int x, int y) {
            int distance = 0;
            
            while (x > 0 || y > 0) {            
                int a = x & 0b1;
                int b = y & 0b1;
                
                if ((a ^ b) == 1) {
                    distance++;
                }
                
                x = x >> 1;
                y = y >> 1;
            }
            
            return distance;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.