This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

The Hamming distance between two integers refers to the number of different positions of the two numbers corresponding to the binary bits.

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

Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0 0) ↑ arrows indicate the different locations of the corresponding binary bits. Source: LeetCode Link: https://leetcode-cn.com/problems/hamming-distance Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • This topic is a simple topic, mainly on the knowledge of bitwise operation investigation. Through the explanation of hamming distance, we find that it is the application of xOR operation.
  • Xor is 1 only if the corresponding position is different.
  • The temporary variable is obtained by xor operation, and then the number of bits 1 is counted, which is the answer to the question.
  • In bitwise operations, n & (n-1) can change the least significant 1 to 0

AC code

    public int hammingDistance(int x, int y) {
        int ans = 0;
        int n = x ^ y;
        while(n ! =0) {
            ans++;
            n &= (n - 1); 
        }
        return ans;
    }
    
    
    public int hammingDistance1(int x, int y) {
        int n = x ^ y;
        return Integer.bitCount(n);
    }
Copy the code

Submit tests:

conclusion

  • The time complexity of the above algorithm code is O(n) and the space complexity is O(1).
  • In Java, bitCount is generally used to count the number of bits 1. Let’s take a look at the implementation of bitCount.
    /**
     * Returns the number of one-bits in the two's complement binary
     * representation of the specified {@code int} value.  This function is
     * sometimes referred to as the <i>population count</i>.
     *
     * @param i the value whose bits are to be counted
     * @return the number of one-bits in the two's complement binary
     *     representation of the specified {@code int} value.
     * @since1.5 * /
    public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }
Copy the code

BitCount is also a bit operation, which is a little bit deeper than my implementation.

  • This algorithm topic I am not the first time to do, the second time is obviously faster than the first time to do a lot of algorithm topic to do a few more times, to master the better!
  • Stick to the daily question, come on!