C ++ solution use bitwise operations without loop


  • 1
    G
    int hammingDistance(int x, int y) {
            int z = (x ^ y);
            int m1 = 0x55555555;
            int m2 = 0x33333333;
            int m3 = 0x0f0f0f0f;
    
            z = (z & m1) + ((z >> 1) & m1);
            z = (z & m2) + ((z >> 2) & m2);
            z = (z & m3) + ((z >> 4) & m3);
            z += (z >> 8);
            z += (z >> 16);
    
            return z & 0x3f;
        }
    

  • 1
    E

    Can you explain a litter?


  • 0
    M

    I made some research on this solution due to my own curiosity. It is basically a formula solution of Hamming distance. This wiki page https://en.wikipedia.org/wiki/Hamming_weight describes how the algorithm works.

    Firstly, m1, m2, m3 could be written in binary form as: 01010101..., 00110011...., 0000111100001111.... In fact ,we could add more m according to the same rules.

    This part of code

    (z & m1) + ((z >> 1) & m1)
    

    could be break into three steps:

    1. store all digits with odd index(right to left), for example, (1011 & m1) will get (0001),
    2. similarly, store all digits with even index((1011 >> 1) & m1) will get (0101)
    3. add them together: (0001 + 0101 = 0110). Divide 0110 into : (01 10) and change them into decimal: (1 2)

    We could regard (z & m1) + ((z >> 1) & m1) as a "folding" function. Regard the original digit as an array of 1-digit, binary numbers: [1, 0, 0, 1] , the folder will change the original array into 2-digit, binary numbers: [01(1), 10(2)].

    Similarly, folder functions also use m2, m3.... By applying the folder function simutaniously, the array will become 4-digit, 8-digit...until reach any sufficiently large number of digit (sorry for my english but hope you could understand). Finally it will be folded into an array with only one element, which is the result of Hamming distance.


Log in to reply
 

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