> For the complete documentation index, see [llms.txt](https://yangsx95.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/wei-yun-suan-yi-ji-wei-tu.md). # 位运算以及位图 计算机中的数在内存中都是以二进制形式进行存储的，用位运算就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。 ## 位操作符 ### 与& ``` 1 0 0 1 1 1 1 0 0 1 ------------------------------ 1 0 0 0 1 与运算 两个位都是 1 时，结果才为 1，否则为 0 ``` ### 或 | ``` 1 0 0 1 1 1 1 0 0 1 ------------------------------ 1 1 0 1 1 或运算 两个位都是 0 时，结果才为 0，否则为 1 ``` ### 异或运算 ^ **即无进位相加** ``` 1 0 0 1 1 1 1 0 0 1 ----------------------------- 0 1 0 1 0 异或运算，两个位相同则为 0，不同则为 1 ``` 1. `0 ^ N = N`, `N ^ N = 0` 2. 异或运算满足交换律与结合律 > 使用无进位相加理解上述两个性质非常容易 ### 取反运算 \~ ``` 1 0 0 1 1 ----------------------------- 0 1 1 0 0 取反运算，0 则变为 1，1 则变为 0 ``` ### 左移运算 << ``` int a = 8; a << 3; 移位前：0000 0000 0000 0000 0000 0000 0000 1000 移位后：0000 0000 0000 0000 0000 0000 0100 0000 左移运算，向左进行移位操作，高位丢弃，低位补 0 ``` * 对一个数进行左移一次相当于 `* 2` * 左移n次，相当于`* (2 ^ n)` ### 右移运算 >> ``` unsigned int a = 8; a >> 3; 移位前：0000 0000 0000 0000 0000 0000 0000 1000 移位后：0000 0000 0000 0000 0000 0000 0000 0001 右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位 ``` * 对一个数右移一次相当于 `/ 2` * 右移n次，相当于 `/ (2 ^ n)` ### 无符号右移运算 >>> ``` unsigned int a = -1; a >>> 1; 移位前：0000 0000 0000 0000 0000 0000 0000 1000 移位后：0000 0000 0000 0000 0000 0000 0000 0001 无符号右移运算，向右进行移位操作，高位补 0 ``` ## 负数的表示 计算机32位int值，如果是无符号整型，可以表示的数字范围位`0 ~ 2^32-1`，如果是有符号整型，可表示的数字范围为`-2^31 ~ 2^31-1`，包含0，他们都共可以表示 `2 ^ 32`个数字。 无符号整型将所有32位都作为值存储，而有符号整型则将最高位作为符号位，当符号位为0代表该数字为非负数（可能为0以及正数），如果符号位数字为1，代表该数字为负数，比如在Java中： ```java print(Integer.MAX_VALUE); // 01111111111111111111111111111111 int最大值 正值 print(Integer.MIN_VALUE); // 10000000000000000000000000000000 int最小值 负值 print(1); // 00000000000000000000000000000001 print(-1); // 11111111111111111111111111111111 ``` 负数二进制表示的计算： ``` 假设负数 -1： 最高位也就是符号位为1，也就是 100....00 后面的31位表示数字值，对绝对值使用取反加一计算： 原值 => 100....01 取反 => 111....10 加一 => 111....11 这个值就是 -1 的二进制表示 ---------- 假设负数位 Integer最小值也就是 -2^31 最高位也就是符号位为1，也就是 100....00 后面的31位表示数字值，对绝对值使用取反加一计算： 原值 => 1100....000 注意，这里溢出一位 取反 => 1011....111 加一 => 1111....111 结果 => 1111....11 溢出的一位直接去除，这个值就是 -2^31的二进制表示 ``` **取反加一就是二进制的补码。** **为什么负数要使用二进制补码的形式？** > 参考： > > 总结：一种巧妙地设计，也是一种规定，为了提高二进制计算的效率 ## 常见的位运算问题 ### 32位int转换为二进制字符串 ```java /** * 打印数字的二进制表现字符串 */ public static void print(int num) { for (int i = 31; i >= 0; i--) { System.out.print((num & (1 << i)) == 0 ? "0": "1"); } System.out.println(); } ``` > 说明：便利32位int的每一位，将每位的状态打印。比如，第一位与 `100....00`相与，可得到该数第一位的状态；第二位与`0100...0`相与，可得到第二位的状态，一直到第最后一位，从 31 到 0。 ### 交换数字（异或） ```java a ^= b; b ^= a; a ^= b; ``` **原理：** ```java int a = x; int b = y; a ^= b; // a = x ^ y; b ^= a; // b = y ^ x ^ y; b = x; a ^= b; // a = x ^ y ^ x; a = y; ``` **注意：** ```java public static void swap(int[] arr, int i, int j) { arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; } swap(arr, 0, 1); // 正确 swap(arr, 0, 0); // 错误，arr[i] 与 arr[j] 会都变为0，这是因为arr[i] 与 arr[j] 共用一块内存，如下 // arr[i] ^= arr[j]; // arr[i] = x ^ x; arr[i] = 0; // arr[j] ^= arr[i]; // arr[j] = 0 ^ 0; arr[j] = 0; // arr[i] ^= arr[j]; // arr[i] = 0 ^ 0; arr[i] = 0; ``` ### 判断奇偶数 ```c if(0 == (a & 1)) { //偶数 } ``` ### 正负切换（补码） ```c int reversal(int a) { return ~a + 1; } ``` ### 绝对值 ```c int abs(int a) { int i = a >> 31; // 获取符号位 return i == 0 ? a : (~a + 1); // 符号位为0=>正数不变返回，符号位为1=>负数取反加一返回 } ``` ### 高低位交换 ``` 34520的二进制表示： 10000110 11011000 将其高8位与低8位进行交换，得到一个新的二进制数： 11011000 10000110 其十进制为55430 ``` ```c unsigned short a = 34520; a = (a >> 8) | (a << 8); // 1. a >> 8 得到高8位 00000000 10000110 // 2. a << 8 得到低8位 11011000 00000000 // 3. (a >> 8) | (a << 8) 得到 11011000 10000110 ``` ### 统计二进制中 1 的个数 ```java /** * 统计二进制数中1的个数 */ public static int count(int num) { int count = 0; for (int i = 31; i >= 0; i--) { count += (num & (1 << i)) == 0 ? 0 : 1; } return count; } ``` 统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 `a &= (a-1)`的结果： * 第一次：计算前：`1000 0110 1101 1000` 计算后：`1000 0110 1101 0000` * 第二次：计算前：`1000 0110 1101 0000` 计算后：`1000 0110 1100 0000` * 第二次：计算前：`1000 0110 1100 0000` 计算后：`1000 0110 1000 0000` 我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计： ```c count = 0 while(a){ a = a & (a - 1); count++; } ``` ### 位运算实现加减乘除 计算机底层都是使用位运算实现加减乘除。 #### 加法 ``` a = 46; => 0010 1110 b = 20; => 0001 0100 // 使用异或获取无进位相加的结果 a ^ b => 0011 1010 => 58 // 由上面可知，进位信息位于第三位 // 可以使用先&获取同为1的位置，再左移获取进位信息 a & b => 0000 0100 a & b << 1 => 0000 1000 => 8 // 加法和就等于 无进位相加和 + 进位 58 + 8 = 66 // 继续使用上述方式计算 58 + 8 a = 58; => 0011 1010 b = 8; => 0000 1000 a ^ b; => 0011 0010 => 50 a & b; => 0000 1000 a & b << 1 => 0001 0000 => 16 // 继续使用上述计算方式计算 50 + 16 a = 50; => 0011 0010 b = 16; => 0001 0000 a ^ b; => 0010 0010; => 34 a & b; => 0001 0000; a & b << 1; => 0010 0000; => 32 //继续使用上述计算方式计算 34 + 32 a = 34; => 0010 0010; b = 32; => 0010 0000; a ^ b; => 0000 0010; => 2 a & b; => 0010 0000; a & b << 1; => 0100 0000; => 64 // 继续使用上述计算方式计算 64 + 2 a = 64; => 0100 0000; b = 2; => 0000 0010; a ^ b; => 0100 0010; => 66 a & b; => 0000 0000; 没有进位，那么此时a ^ b 的结果就是该加法的结果。 ``` java实现： ```java public static int add(int a, int b) { int sum = a; while (b != 0) { sum = a ^ b; b = (a & b) << 1; a = sum; } return sum; } ``` #### 减法 ```java // 减法就是 a + (-b)， 一个数的相反数可以用 ~b + 1来表示 public static int minus(int a, int b) { return add(a, add(~b, 1)); } ``` #### 乘法 乘法的实现方式是乘法的竖式表达程序化： ``` 23 x 12 ---- 46 23 ---- 276 二进制表现相同： 10111 x 1100 ----------- 00000 00000 10111 10111 ----------- 100010100 => 276 ``` 程序化： ```java // 乘法 public static int multi(int a, int b) { int bi; int result = 0; int count = 0; while (count < 32) { bi = b & (1 << count); if (bi != 0) { result = add(result, a << count); } count++; } return result; } // 乘法更简单的实现 // b每次向右侧移动一位，即可取到某位的状态 public static int multi2(int a, int b) { int res = 0; while (b != 0) { if ((b & 1) != 0) { res = add(res, a); } a <<= 1; b >>>= 1; } return res; } ``` #### 除法 ``` 举例说明 41 / 3 3 * 2 ^ 0 = 3 < 41 3 * 2 ^ 1 = 6 < 41 3 * 2 ^ 2 = 12 < 41 3 * 2 ^ 3 = 24 < 41 3 * 2 ^ 4 = 48 > 41 商=2^3 对余数继续除： 41 - 24 = 17 17 / 3 3 * 2 ^ 0 = 3 < 17 3* 2 ^ 1 = 6 < 17 3 * 2 ^ 2 = 12 < 17 3 * 2 ^ 3 = 24 > 17 商 = 2^3 + 2^2 对余数继续除 17 - 12 = 5 3 * 2 ^ 0 = 3 < 5 3 * 2 ^ 1 = 6 > 5 商 = 2^3 + 2^2 + 2^0 5 - 3 = 2 2 < 3 不继续除 所以，41 / 3 = 2^3 + 2^2 + 2^0 = 13 ``` 使用除2的方式是因为2可以使用位运算替代。这种方式实际就是不断的减去被除数，并计算被减的次数。 Java代码实现如下： ```java ``` ### 控制某一位 假设有二进制数`1011 0110`： 1. 控制这个二进制数的最高位变为0： ``` 1011 0110 &0111 1111 0011 0110 ``` 2. 控制这个二进制数的最低位变为1： ``` 1011 0110 |0000 0001 1011 0111 ``` java实现： ```java /** * 设置二进制数的某一位 * @param num 二进制数 * @param pos 位置 * @param flag true => 1， false => 0 */ public static int set(int num, int pos, boolean flag) throws IllegalArgumentException{ if (pos < 0 || pos > 31) { throw new IllegalArgumentException(); } if (flag) { num |= (1 << pos); return num; } num &= ~ (1 << pos); return num; } ``` ### 位图的实现 Java: ```java static class BitMap { // 1个long类型可以存储64位 // 使用一个long类型数组存储bit位图 private final long[] bits; // 根据max确定数组的长度 // 如果 max 属于 0 ~ 63 则数组长度为1 // 如果 max 属于 0 ~ 127 则数组长度为2 public BitMap(int max) { if (max < 0) throw new IllegalArgumentException(); bits = new long[(max + 64) >> 6]; // 等同于 (size + 64) / 64 } // 将某个位置置为1，位置索引从0开始 public void add(int num) { // 1. 确定num位置属于数组的第几个整数元素： 0/64=0, 64/64=1, 127/64=1, 128/64=2 // 故元素位置= num / 64 也就是 num >> 6 // 2. 确定num位于已确定的整型元素的第几位： 0%64=0, 1%64=1, 127%64=63, 128%64=0 // 故num位置位于整型元素的第 num%64位。num%64 等同于 num&63： // num%64等同于只保留二进制的最后6位，前面的位数全部去除，所以 num & 63 = num % 64 // 3. 将指定位置1，使用 |，比如将第2位置1 // 0000 | 0100 = 0100 // 0100 => 1 << (num & 63) // 故结果如下： bits[num >> 6] |= (1L << (num & 63)); } public void delete(int num) { // 1. 确定num位置属于数组的第几个整数元素: num >> 6 // 2. 确定num位于已确定的整型元素的第几位: num % 64 => num & 63 // 3. 将指定位置0，使用&，比如将第二位置0 // 1111 & 1011 = 1011 // 1011 => ~0100 // 故结果如下 bits[num >> 6] &= ~(1L << (num & 63)); } public boolean contains(int num) { // 1010 & 0100 => 0000 说明第二位是0，否则第二位是1 return (bits[num >> 6] & (1L << (num & 63))) != 0; } } ``` ## 面试题 ### 异或 **一个数组中有一个数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这个数字？** ```java // 给定数组 [4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4] // 其中 1共有4个，2共有3个，3共有4个，4共有2个 // 找到个数为奇数的数字，也就是2 // 使用异或 public static void main(String[] args) { int[] arr = {4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4}; int t = 0; for (int i = 0; i < arr.length; i++) { t ^= arr[i]; } System.out.println(t); // 2 } ``` 原理： 1. 满足交换律，所以 `4, 1, 3, 3, 2, 1, 3, 1, 2, 3, 2, 1, 4`即为：`1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4` 2. 相同的数字异或为0， 所以上述数字偶数个的都会被异或为0，奇数个的最中会剩余一个数字 *** **怎么将一个int类型的数，提取出他二进制最右侧的1来？** ```java public static void main(String[] args) { int N = 200; System.out.println(Integer.toBinaryString(N)); // 11001000 // 提取最右侧的1，使用公式：N & ((~N) + 1) int result = N & ((~N) + 1); System.out.println(Integer.toBinaryString(result)); // 1000 } ``` 推算过程： ``` 原数 .... 0000 0000 1100 1000 取反 .... 1111 1111 0011 0111 加一 .... 1111 1111 0011 1000 相与 .... 0000 0000 0000 1000 ``` *** **一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数？** ```java // 假设两个奇数为 a 和 b // eor = 将数组中所有元素相互异或 // eor = a ^ b != 0 // 因为eor != 0，故eor 在至少有一个位置上一定有1，所以 a 和 b 在这些位置上的 0 与 1 的状态一定不一致 // 取eor出最右侧的1，与数组的所有元素相与，可以得出该位置为1的所有元素，其中一定含有 a 或者 b // 将这些元素再次相互异或，可以得到 a 或者 b， 根据 eor = a ^ b; a = eor ^ b; 故而得到 a 和 b // 代码如下： // 假设两个奇数为 a 和 b // eor = 将数组中所有元素相互异或 // eor = a ^ b != 0 // 因为eor != 0，故eor 在至少有一个位置上一定有1，所以 a 和 b 在这些位置上的 0 与 1 的状态一定不一致 // 取eor出最右侧的1，与数组的所有元素相与，可以得出该位置为1的所有元素，其中一定含有 a 或者 b // 将这些元素再次相互异或，可以得到 a 或者 b， 根据 eor = a ^ b; a = eor ^ b; 故而得到 a 和 b // 代码如下： public static void printOddNum2(int[] arr) { int eor = 0; for (int i = 0; i < arr.length; i++) { eor ^= arr[i]; } int rightOne = eor & (~eor + 1); int aOrB = 0; for (int i = 0; i < arr.length; i++) { if ((arr[i] ^ rightOne) == 0) { aOrB ^= arr[i]; } } System.out.println(aOrB + " " + (eor ^ aOrB)); } ``` *** **找到数字N的二进制的含有1的数量？** ```java // 以rightOne作为判断条件 public static int bit1Count(int n) { int count = 0; int rightOne; while (true) { // 找到最右侧的1 rightOne = n & (~n + 1); if (rightOne == 0) { return count; } count ++; // 抹掉最右侧的1 n ^= rightOne; } } // 以n数字作为判断条件 public static int bit1Count2(int n) { int count = 0; int rightOne; while (n != 0) { // 找到最右侧的1 rightOne = n & (~n + 1); count ++; n ^= rightOne; } return count; } ```