位运算及其使用技巧

一、基础认识

计算机底层运算时，都是二进制数据补码间的运算，也就是先将原码转成补码进行运算的，补码间进行运算，得到的也是补码，输出时就再将补码转换为原码(正数的补码就是原码).
 
位运算能够对整数在内存中的二进制位直接进行操作，因此在很多时候使用位运算能大大提高程序的性能.

注: 位运算操作的二进制位包含符号位，也就是不区分符号位

*(为方便演示，以下用 8 位二进制数进行运算)
 

1.1 按位与: &

每一个对应二进制位都进行与运算，例如: -3&1，如下:

-3(10) -> 10000011(原码) -> 11111100(反码) -> 11111101(补码)
1(10) -> 00000001(原码) -> 00000001(反码) -> 00000001(补码)
-3的补码是: 11111101, 1的补码是: 00000001
11111101 & 00000001 -> 00000001(补码) -> 00000001(原码) -> 1(十进制)
1
2
3
4

 

1.2 按位或: |

每一个对应二进制位都进行或运算。例如: -2|5，如下:

-2的补码是: 11111110, 5的补码是: 00000101
 11111110 | 00000101 -> 11111111(补码) -> 10000001(原码) -> -1(10)
1
2

 

1.3 按位异或: ^

不同为 1，相同为 0。例如: -5^1，如下:

-5的补码是: 11111011, 1的补码是: 00000001
11111011 ^ 00000001 -> 11111010(补码) -> 10000110(原码) -> -6(十进制)
1
2

 

1.4 按位取反：~

每一个二进制位进行取反。例如: ~3，如下:

-3的补码是: 11111101
~11111101 -> 00000010(补码) -> 00000010(原码) -> 2(十进制)
1
2

 

1.5 左移: <<

高位丢弃，低位补0
(左移 n 位就是在原数乘以 2^n（2的n次方))

3的补码是: 00000011()
(00000011 << 1) -> 00000110(补码) -> 6(十进制)
1
2

 

1.6 右移: >>

低位丢弃，高位补0
(右移 n 位就是在原数除以 2^n（2的n次方），取整)

4的补码是: 00000100(补码)
(00000100 >> 1) -> 00000010(补码) -> 2(十进制)
1
2

 

二、使用技巧

2.1 按位与:

&、得到 x 的第 i 个二进制位:

比如: 743，它的二进制是: 00000000 00000000 00000010 11100111
其中第 0 位是 1，第 5 位是 0，第 6 位是 0

可以使用 (x >> i) & 1 来得到一个数的第 i 个二进制位，i 从 0 开始(0,1,2,3…)

1.比如，(743 >> 4) & 1，x >> 5 -> 0000 00000000 00000000 00000010 1110(0111)，
0000 00000000 00000000 00000010 1110 & 00000000 00000000 00000000 00000001
进行与运算即为: 00000000 00000000 0000000 00000001
 
总的来说，就是将一个数向右移动 i 位，取得第 0 位即为原先的数的第 i 位

 
&、将 x 的二进制表示的最后一个 1 置为 0:

x & (x- 1 )
例如: 8，二进制表示是: 1010，
x - 1 -> 1010 - 1 = 1001，可以发现，原来的二进制数最后一个 1 之后的位与改变后的数对应位上是相反的，此时进行与运算即可消去 1 变为 0

 

2.2 按位或:

&、在 x 的尾部补一个二进制位(0或1):

如: x = 5，即 101₂，然后在 101₂ 的尾部添加 0 或 1

int x = 5;
int n = 0; // 或者 1
x <<= 1; // 101 -> 1010
x |= n; // 1010 | 0000(n=0) = 1010 ,或者 1010 | 0001(n=1) = 1011
1
2
3
4

 

2.3 异或：

&、三个性质
leetcode136:只出现一次的数字:

给出一个数组，其中只有一个数字只出现1次，其它数字均出现了2次，请找出这个只出现一次的数字

异或运算有如下三个性质:
1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a^0 = a
2. 任何数和其自身做异或运算，结果是 0，即 a^a = 0
3.异或运算满足交换规律和结合律，即 a^b^a = b^aa = b^(a^a) = b^0 = b

public class Solution {

     * 假设数组中有 2m+1 个数，其中有 m 个数各出现两次，一个数出现一次。令 a1、a2、.、am 为出现两
     * 次的 m 个数，αm十1 为出现一次的数。根据性质3，数组中的全部元素的异或运算结果总是可以写成如下
     * 形式：
     *  (a1⊕a1）⊕(a2⊕a2）⊕·⊕(am⊕am）⊕am+1
     * 根据性质2和性质1，上式可化简和计算得到如下结果：
     *  0⊕0⊕··⊕0⊕am+1=0m+1
     * 因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18