461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

The above arrows point to positions where the corresponding bits are different.

My Code:

public class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int count = 0;
        while(xor != 0){
            xor = xor & (xor - 1);
            count++;
        }
        return count;
    }
}

Idea:
1. xor to get different bits;
2. count the bits which is one;

Skills:
How to count bits that is one
1) x & (x – 1)to remove the last one。count x & (x – 1) until the number to be zero, to get the count of how many one has been removed.
2)

</pre>
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i<<span class="hljs-number">32</span>;i++) <span class="hljs-keyword">count</span> += (xor >> i) & <span class="hljs-number">1</span>;

3)

</pre>
<span class="hljs-keyword">return</span> Integer.bitCount(x ^ y);

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s