Java Simple Three Line Solution with Complete Explaination


  • 0
    M
    • First perform XOR to find out all the bits where the corresponding bits differ in x and y. All the bit positions where the corresponding bits differ will be set to 1.
      Fact table for XOR for refresher.
      1 ^ 0 = 1
      0 ^ 1= 0
      1 ^ 1 = 0
      0 ^ 0 = 0
    • In the resulting bit pattern count how many times bit "1" was spotted. If we AND n with n-1, it takes out the "1" bit from the least significant position.

    Why is that?
    When we subtract 1 from any number, the carry will travel until it finds the first "1" bit. That 1 bit will become 0 and all 0 bits in between will turn to 1.
    Bit Pattern of 12 => 1100
    Bit Pattern of 11 => 1011
    Notice that all 0 bits before first encounter of 1 from 12 turned to 1 due to carry of (0-1) and the carry was satisfied by transforming third "1" bit to 0. All the bits after this point remains exactly same in n and n-1. So essentially it took out the "1" bit from least significant position. If we keep on doing this we will hit number 0. The only time it will need full 31 iterations is when all the bits are 1.

    public class Solution {
        public int hammingDistance(int x, int y) {
         int num = x ^ y, count = 0; 
         for(;num > 0; num &= (num-1),count++);
         return count;
        }
    }
    

Log in to reply
 

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