1. Numbers that appear only once

This tip comes from Leetcode problem 136. In an array where all other numbers appear twice and only one number appears once, how to find it?

The code is as follows:

    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
Copy the code

The idea of this problem lies in xOR operations in bit operations. In xOR operations:

1 ^ ^ 1 = 0, 0 = 1, 0 ^ 1 = 1, 0 ^ 0 = 0Copy the code

From the results of the xOR operation, it is not difficult to conclude that the xor result of the same digit is 0 if it occurs even times, and 1 if it occurs odd times.

a^a^b => (a^a)^b => 0^b => b
Copy the code

So we can do xor.

2. The number II that appears only once

Again, this tip comes from LeetCode, on problem 137. Compared to the previous problem, in this problem, all the other numbers appear 3 times, but only one number appears once. How can we find it?

So after the last problem, we know that we can use xOR to get an odd number of times. So if the same odd number of times occurs, how to distinguish between 1 and 3 times becomes the key to solve the problem. The code is as follows:

    public int singleNumber(int[] nums) {
        int seenOnce = 0, seenTwice = 0;
        for (int num : nums) {
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }
        return seenOnce;
    }
Copy the code

In this case we can use two masks to record the occurrence of 1 and 2 digits respectively.The calculation process is shown in the figure above. When a number appears only once, the first mask is recorded. When it occurs a second time, the first mask disappears and the second mask is recorded. When it appeared three times, both masks disappeared. So you can tell the difference between 1 and 3.

3. Count the number of 1’s in int binary

So to do a direct count we need to do 32 bit operations plus 32 judgments plus 0 minus 32 addition operations to figure out how many ones are in binary. So is there a way to use fewer computational statistics? The answer is in the JDK source code.

    public static int bitCount(int i) {
        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

The above code is taken from Integer’s bitCount method. Using the above method, only 15 operations are needed to calculate the result.

At first glance, the code looks a little hazy. Don’t panic. Let me take inventory. To figure out how many 1’s there are in 32-bit binary, let’s think about, is there a way to calculate the number of 1’s in binary in a single count, regardless of how many bits there are? The answer is yes. We can start by looking at how 2-bit binary counts the number of 1s:

    public int bitCount(int i) {
        return i - ((i >> 1) & 1);
    }
Copy the code

If I is in the range 0 to 3 (binary 0, 01, 10, 11), you can directly calculate the number of 1’s in the binary of I. So in this case, the first step makes sense.

i = i - ((i >>> 1) & 0x55555555);
Copy the code

This line of code just amortizes our two-bit binary computation into 32-bit binary computation. That’s 16 sets of results.

Enter I = 11 01 I >>>1 = 01 10 (I >>>1) & (01 01) = 01 00 I = 01 00 = 10 01 the result is that the first two digits have two 1s and the last two digits have only one 1.Copy the code

Once you’ve done the first step, it’s easy to just add up the results that you’ve divided among the 16 groups. Here’s an example:

Enter I = 10 01 I &0011 = 00 01 I >>>2 = 00 10 00 01 + 00 10 = 0011 To merge the result of each two bits, the result of each four bits is merged.Copy the code

How many merges does it take to go from 2 bits to 32 bits? 2->4->8->16->32 to get the final result.

4. Check whether int overflows after calculation

In the calculation of numbers, it is often necessary to judge whether two numbers overflow after adding or subtracting. It can be buggy if you don’t judge. So this judgment process, we can also do with bit operations.

Additive judgment

    public static int addExact(int x, int y) {
        int r = x + y;
        if (((x ^ r) & (y ^ r)) < 0) {
            throw new ArithmeticException("integer overflow");
        }
        return r;
    }
Copy the code

Code excerpted from JDK source math.addexact; We know that the sum of two numbers with different signs will not overflow. Overflow occurs only when numbers of the same sign add up. So we can talk separately about adding two positive numbers and two negative numbers.

First of all, two positive numbers don’t add up to a negative number, but if you overflow, you get a negative number. So we can make a judgment based on that. In the code above, r is the result of addition. If r overflows, the leftmost bits of r must be 1. The leftmost bits of x and y, which are positive numbers, must be 0. So when x and y are both greater than 0, (x ^ r) ^ (y ^ r)) is less than 0, you definitely overflow.

The same thing with negative numbers, if you add two negative numbers and you get a positive number, that’s definitely not normal.

For a plus and a minus, (x ^ r) &(y ^ r)) must also be greater than 0.

Subtract judgment

    public static int subtractExact(int x, int y) {
        int r = x - y;
        if (((x ^ y) & (x ^ r)) < 0) {
            throw new ArithmeticException("integer overflow");
        }
        return r;
    }
Copy the code

It’s the same thing as adding. Two subtractive operations of the same symbol do not overflow. So x to the y is the same sign. If it’s the same sign, it’s not going to overflow. If it’s a different sign, compare the result with the sign of x. If the result is different from the sign of x, then an overflow has occurred.