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