When I learn the discussion of Leetcode 1755, I found a really interesting line
sum+= nums[j]*((i>>j)&1);
And I don’t know what’s the meaning. Then I realize I need to get deep thought about Bitwise Operators.
（i>>j&1) means in the binary of i, count from right to left and take the value at the position of j+1. If we write in Java code, it should be:

1
2
3
4
int a = i;
a = a / (int)pow(2, j);
if (a % 2 == 0)return 0;
else return 1;
  1. Determine the odd and even number
    If a number n is expressed as a binary number, we only need to determine whether the last binary digit is 1 or 0. If it is 1, it represents an odd number, otherwise it is an even number. code show as below:
    1
    2
    3
    if(n & 1 == 1){
        // n is odd
    }
  2. Exchange two numbers without extra space
    1
    2
    3
    x = x ^ y; // (1)
    y = x ^ y; // (2)
    x = x ^ y; // (3)
    We all know that the result of XOR two identical numbers is 0, that is, n ^ n = 0, and any number after XOR 0 is equal to itself, that is, n ^ 0 = n.

So we use x in (1) to represent x in (2), there are: y = x ^ y = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x The value is assigned to y.

For (3), the derivation is as follows: x = x ^ y = (x ^ y) ^ x = (x ^ x) ^ y = 0 ^ y = y, so the value of y is assigned to x.

  1. Find the non-repeated number

Many people may use a hash table to store this question. Each time it is stored, record the number of times a certain number appears, and finally traverse the hash table to find out the number of times it appears only once. The time complexity of this method is O(n), and the space complexity is also O(n).

In fact, this question can also perform bitwise operations. We can XOR all the integers. Since the result of the XOR of two identical numbers is 0, the result of the XOR of a number with 0 is itself, so The result of the exclusive OR is the number that appears only once. For example, this set of data is: 1, 2, 3, 4, 5, 1, 2, 3, 4. Five of them appear only once, and the others appear twice. XOR all of them. The result is as follows:

1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 1 ^ 2 ^ 3 ^ 4 = (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 0 ^ 0 ^ 5 = 5

1
2
3
4
5
6
7
int find(int[] nums){
    int tmp = nums[0];
    for(int i = 1;i < nums.length; i++)
        tmp ^= arr[i];
    
    return tmp;
}
  1. m to the n power

If you directly multiply n m times, the time complexity is O(n).
For example, n = 13, the binary number of n is represented as 1101, then the 13th power of m can be broken down as: m ^ 1101 = m ^ 0001 * m ^ 0100 * m ^ 1000. We can read 1101 bit by bit through & 1 and >>1. When it is 1, the multiplier represented by this bit is accumulated to the final result. The final code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
int pow(int n) {
    int sum = 1;
    int tmp = m;
    while(n != 0) {
        if(n & 1 == 1)
            sum *= tmp;
        
        temp *= temp;
        n >>= 1;
    }
    return sum;
}

Time complexity: O(logn)

  1. Find the largest power of 2 exponent not greater than N

For example, N = 19, then the conversion to binary is 00010011 (here for convenience, I use 8-bit binary to represent). Then the number we are looking for is to keep the leftmost 1 in the binary, and all the following 1s become 0. That is, our target number is 00010000. So how to get this number? The corresponding solution is as follows:

  1. Find the leftmost 1 and change all 0s on the right to 1

  2. Add 1 to the obtained value to get 00100000 that is 00011111 + 1 = 00100000.

  3. Move the obtained 00100000 one place to the right to get 00010000, that is, 00100000 >> 1 = 00010000.

So the question is, how can I get the 0 after the 1 in the leftmost 1 in the first step?

1
2
3
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;

It can be obtained by shifting n to the right and doing an OR operation. Let me explain. Let’s assume that the leftmost 1 is at the k-th position in the binary digits (counting from left to right). After shifting n to the right by one place, the k+1-th position in the result must also be 1. , And then do an OR operation on the result of n and the right shift, then the kth and k + 1 digits of the result obtained must be 1; in the same way, again shift n to the right by two bits, then the kth result is obtained +2 and k+3 must be 1, and then do the OR operation again, then you can get k, k+1, k+2, k+3 are all 1, and so on…

The final code is as follows:

1
2
3
4
5
6
7
int findN(int n){
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8 // Integer should be 32, I assume 8 bit before. 
    return (n + 1) >> 1;
}

Time complexity should be O(1)

Some Leetcode practice: LC89