From Ground Up Completely Explained Java Solution

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

}
``````

}

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