C# - Simple solution


  • 8
    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!

  • 2
    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?


Log in to reply
 

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