Hamming Distance XOR SOLUTION (C++)


  • 1
    V

    The approach is simple we just need to find out at how many bits the number differ so we can just take the XOR of the numbers and count the number of bits in it.

    public:
        int hammingDistance(int x, int y) {
            int xr = x^y;
            int cnt = 0;
            while(xr > 0){
                if(xr & 1){
                    cnt++;
                }
                xr >>= 1;
            }
            return cnt;
        }
    };
    
    Time Complexity of the above solution : O(log2(N)).
    
    We can make the counting of bit in O(1) 
    using __builtin_popcount() function.
    
    
    public:
        int hammingDistance(int x, int y) {
            return __builtin_popcount(x^y);
        }
    };

  • 0
    L

    What is your evidence to say that __builtin_popcount(x^y) works in O(1)?


Log in to reply
 

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