From Ground Up Completely Explained Java Solution


  • 0
    Y

    I've been trying to teach myself bit manipulation. I have found that it's been really hard to find comprehensive explanations for bit manipulation problems as a lot of the procedures are non-intuitive when you first start learning them. Thought I would post for self reference as well as for anyone who is in the same boat as me.

        public int hammingDistance(int x, int y) {
            //Problem: We want to find the number of places where bit value of X does not equal y
            //Recall that when two bits are the same the XOR of the two bits is 0 and different bits will be 1
            //Lets Look at the XOR table
            // X | Y | X^Y
            // 1 | 1 |  0
            // 0 | 1 |  1
            // 1 | 0 |  1
            // 0 | 0 |  0
            
            //So what do we have to do after we xor the two numbers? 
            //Since we know that the different bits will be 1 we simply just have to count the number of 1's that show up!
             int xor = x ^ y;
             
             //stores the number of 1's
             int count = 0;
             
             //We know integers have 32 bits
             //So for each bit let's check if the number is 1
            for(int i=1; i<33; i++){
             //Let's write function getBit that given an int and a bit index tell's you if that bit in the index is a 1
                if(getBit(xor, i) == true){
                //if the bit is 1 then increment
                count++;
              }
            }
        return count;
    
        }
    //Getbit is one of the basic bit manipulation fuctions that given and integer and the bit within the int tell's you if the bit has a 1 or a 0
    public boolean getBit(int n, int i){
        //How does it work?
        //1.getBit first shifts 1 over i bits for a number where only the i'th bit is 1 ie (00001000)
        //2.then it performs & with n and the shifted number
        //3.recall & only returns 1 in the case where both bits are 1, because (1<<i) is 0's for all indexes except the ith we are basically only doing a comaparison between the ith indexes to see if they're equal to 1
        return (n & (1 << i)) != 0;
        
        //let's look at an example 
        //let's say we have n = 1100 (or 12 in binary)
        //We call getBit(1100,3) to check if the third index is a 1
        //first the program does (1<<3) which ends us up with 0100
        // now we have an (1100 & 0100) = 0100 
        // We see 0100 != 0 therefore the 3'rd bit must have been equal to 1!
        
        //let's look at a case where the ith bit is not 1
        //let's say we have n = 1000 and we call getBit(1000,3)
        //(1<<3) = 0100
        //(1000 & 0100) = 0000
        // 0000 == 0000 therefore the 3rd bit was equal to 0!
        
    }
    

    }


Log in to reply
 

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