/ Java  

Java Bit Operations

All data is stored in binary form in the computer. Bit operations are actually operations on the binary data in memory, so the data processing speed is very fast.

Bit operation basics

There are 6 basic bit operators: And, Or, XOR, Complement, Left Shift, and Right Shift. Their operation rules are as follows:

Symbol Description Rule
& And The result is 1 when both bits are 1
| Or The result is 0 when both bits are 0
^ Xor 0 if both bits are the same, 1 if they are different
~ Complement 0 becomes 1, 1 becomes 0
<< Left shift Each binary is shifted to the left by several bits, the high bits are discarded, and the low bits are padded with 0.
>> Right shift Each binary bit is shifted to the right by several bits.
Unsigned numbers, high-order bits are complemented with 0, and signed numbers.
Each compiler handles the method differently.
Some complement bits (arithmetic right shift), and some complement 0 (logical right shift).

Note:

  • Of these 6 operators, only ~ complement is a monocular operator, and the other 5 are binocular operators.
  • Bit operations can only be used for integer data. Bit operations on float and double types will be reported by the compiler as errors.
  • The bit operator has a lower precedence, so try to use parentheses to ensure the order of operations, otherwise you may get some inexplicable results. For example, to get 2^i + 1 numbers like 1, 3, 5, and 9. It is wrong to write int a = 1 << i + 1; Should be written as int a = (1 << i) + 1;

And (&)

1
2
3
System.out.println(5 & 3);

// Output: 1

5 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0101
3 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0011
                                ———————————————————–
1 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0001

Or (|)

1
2
3
System.out.println(5 | 3);

// Output: 7

5 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0101
3 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0011
                                ———————————————————–
7 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0111

Xor(^)

1
2
3
System.out.println(5 ^ 3);

// Output: 6

5 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0101
3 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0011
                                ———————————————————–
6 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0110

Complement (~)

1
2
3
System.out.println(~5);

// Output: -6

5 convert to binary:   0000 0000 0000 0000 0000 0000 0000 0101
                                ———————————————————–
-6 convert to binary: 1111 1111 1111 1111 1111 1111 1111 1010

Left shift (<<)

1
2
3
System.out.println(5<<2);

// Output: 20

5 convert to binary:   0000 0000 0000 0000 0000 0000 0000 0101
                                ———————————————————–
20 convert to binary: 0000 0000 0000 0000 0000 0000 0001 0100

Right shift (>>)

1
2
3
System.out.println(5>>2);

// Output: 1

5 convert to binary:   0000 0000 0000 0000 0000 0000 0000 0101
                                ———————————————————–
1 convert to binary: 0000 0000 0000 0000 0000 0000 0000 0001

Common bit manipulation tips

Judging parity

Just need to check the least significant bit is 0 or 1, 0 is even and 1 is odd. So we can use if((a & 1) == 0) instead of if(a% 2 == 0) to determine whether a is even. The following program will output all even numbers between 0 and 100:

1
2
3
4
5
for (int i = 0; i < 100; i ++) {
    if ((i & 1) == 0) {
        System.out.println(i);
    }
}

Exchange two numbers

1
2
3
4
5
6
7
8
9
10
11
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;

System.out.println("a  = " + a);
System.out.println("b = " + b);

// output
// a = 2
// b = 1
  1. The first step a^ = b is a = (a^b);
  2. The second step b^ = a is b = b^(a^b). Since the OR operation satisfies the commutative law, b^(a^b) = b^b^a. Since the result of OR of a number and itself is 0 and the OR of any number and 0 is unchanged, b is assigned the value of a
  3. The third step a^ = b is a = a^b. Since the previous two steps show that a = (a^b) and b = a, a = a^b is a = (a^b)^a. So a is assigned the value of b.

Changing the sign

Changing the sign means that positive numbers become negative numbers, and negative numbers become positive numbers. For -11 and 11, you can use the following transformation method to change -11 to 11

1
2
3
4
5
/ 11
[0000 1011] Complement(~)-> [1111 0100]-> Add 1-> [1111 0101] (-11)

// -11
[1111 0101] Complement(~)-> [0000 1010]-> Add 1-> [0000 1011] (11)

So we only need to complement the number and add 1.

1
2
3
int a = -15, b = 15;
System.out.println(~a + 1);
System.out.println(~b + 1);

Bit manipulation tips

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 1. Get int max
System.out.println((1 << 31) - 1); 
System.out.println(~(1 << 31));

// 2. Get int min
System.out.println(1 << 31);
System.out.println(1 << -1);

// 3. Get long max
System.out.println(((long)1 << 127) - 1);

// 4. times 2 operation
System.out.println(10<<1);

// 5. Divide by 2 (negative and odd operations are not available)
System.out.println(10>>1);

// 6. Multiplied by 2 to the power of m
System.out.println(10<<2);

// 7. Divide by 2 to the power of m
System.out.println(16>>2);

// 8. Determine the parity of a number
System.out.println((10 & 1) == 1);
System.out.println((9 & 1) == 1);

// 9. Exchange two variables without temporary variables (interview quiz)
a ^= b;
b ^= a;
a ^= b;

// 10. Take the absolute value (on some machines, the efficiency is higher than n > 0? n: -n)
int n = -1;
System.out.println((n ^ (n >> 31)) - (n >> 31));
/* 
n >> 31 gets the sign of n, if n is positive, n >> 31 is equal to 0, if n is negative, n >> 31 is equal to -1
If n is a positive number, n ^ 0-0 is unchanged. If n is a negative number n ^ -1, the complement of n and -1 needs to be calculated.
Result n changes sign and subtracts 1 from the absolute value, minus -1 is the absolute value 
*/

// 11. Take the maximum of two numbers (on some machines, the efficiency is higher than a > b? a : b)
System.out.println(b&((a-b)>>31) | a&(~(a-b)>>31));

// 12. Take the minimum of two numbers (on some machines, the efficiency is higher than a > b? b : a)
System.out.println(a&((a-b)>>31) | b&(~(a-b)>>31));

// 13. Determines whether the signs are the same (true means x and y have the same sign, false means x, y have the opposite sign.)
System.out.println((a ^ b) > 0);

// 14. Calculate the nth power of 2> 0
System.out.println(2<<(n-1));

// 15. Determine whether a number n is a power of two
System.out.println((n & (n - 1)) == 0);
/* If it is a power of 2, n must be 100 ... n-1 is 1111 ....So the result of the AND operation is 0 */

// 16. Average two integers
System.out.println((a+b) >> 1);

// 17. From low to high, take the mth bit of n
int m = 2;
System.out.println((n >> (m-1)) & 1);

// 18. From low to high. Set the mth bit of n to 1.
System.out.println(n | (1<<(m-1)));
/*
Shift 1 to the left by m-1 bits to find the mth bit, and get 000 ... 1 ... 000
Or n with this number
*/

// 19. From low to high, set the mth bit of n to 0
System.out.println(n & ~(0<<(m-1)));
/* 
Shift 1 to the left by m-1 bits to find the m-th bit, and invert it to 111 ... 0 ... 1111
AND n and the number again
*/