C# - Simple solution


  • 9
    K
    • Do XOR between the numbers which then gives the difference bits as '1'
    • Calculate those difference no.of bits by bit-END operation on preceding numbers until it is zero
      ...............
      public int HammingDistance(int x, int y) {
      int z = x ^ y;
      int n = 0;
      while(z > 0)
      {
      z = z & (z-1);
      ++n;
      }
      return n;
      }
      ...............

  • 0
    A

    Such great solution it is.
    I just do not understand how it works so well since I have sow it.
    Can you give me a way to understand it?


  • 0
    K
    This post is deleted!

  • 3
    K

    // XOR returns no.of bits that are not same at corresponding positions
    // 2- 0010 and 6 - 0110. Both integers differ at positions (left to right) 3. 2 ^ 6 = 0010 ^ 0110 = 0100
    // You may notice the 1 in the result.
    // Now if we could calculate all those 1's from the result above we get the hamming distance

    // Any two consecutive numbers when written in base2 always differ by either
    // only one bit or differ by all bits - Ex 10000 (16) and 1111(15) differ by all bits
    // (ignore leading zeros) and 1111 (15) 1110(14) differ by 1.Doing & operation on the result
    //continuously will exhaust all 1s and leads to zero. If we want to calculate number of bits in
    //4...0100(4) & 0011(3) becomes zero by then n is incremented by 1 which is our answer


  • 0
    A

    @krishnacs

    Thanks for your kindly help.
    It's amazing that & operation can exhaust one '1' once a time. I've learned a lot from this.
    I'm new comer to Leet Code and this is the first question I learned.
    Thank you again.


  • 0
    A

    @krishnacs XOR does NOT return no.of bits that are not same at corresponding positions. Try it with 7 ^ 8


  • 1
    K

    @Aevil1 Hi Aevil1,
    XOR returns no.of bits that are not same.

    0 ^ 0 - 0
    0 ^ 1 - 1
    1 ^ 0 - 1
    1 ^ 1 - 0

    Your case:

     7   --> 0 1 1 1 
     8   --> 1 0 0 0
    ----------------
    7^8 -->1 1 1 1
    

    You may notice 7 and 8 have 4 bits different. When you do AND operation on this result until it is zero, we get the count of set bits.


  • 0
    X

    @krishnacs : what about difference between 96 (1100000) and 95 (1011111)? It has only 6 differences. can you help me understand it?


  • 0
    Y

    @xXx This is Brian Kernighan’s Algorithm. Google it and there are plenty good explanation articles out there.


Log in to reply
 

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