Use the trick "x & (x-1)" to count 1s in xor


  • 0
    E

    First, x XOR y yields different bit with 1 while same bit is 0.
    Then, x & (x-1) can remove the most right "1" in x. So, we can use this trick to count 1s in the XOR result.

    class Solution {
        public int hammingDistance(int x, int y) {
            /** cheating by using built-in function, haha
            return Integer.bitCount(x ^ y);
            */
    
            int res = 0;
            int num = x ^ y;
            while (num != 0) {
                num = num & (num - 1);  // where magic happens
                res++;
            }
            return res;
        }
    }
    

Log in to reply
 

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