[关闭]
@Catyee 2021-08-01T06:41:33.000000Z 字数 6025 阅读 419

位运算

数据结构与算法

一、 数的二进制表示

计算机中自然数都有原码、反码、补码三种表示方式。
原码就是朴素的二进制表示：

  1. 6的原码：0000 0110 
  2. 从右往左即：0*2^0 + 1*2^1 + 1*2^2 + 0*2^3 = 6

为了表示负数规定原码的最高位标志一个数是正数还是负数：

  1.  1的原码: 0000 0001
  2. -1的原码: 1000 0001

规定正数的原码、反码、补码都是一样的。
而负数的反码是除了最高位以外其它各位取反的结果：

  1.  1的反码：0000 0001
  2. -1的反码：1111 1110

按照规定：正数的补码依然与原码是一样的。
负数的补码是反码加1：

  1.  1的补码：0000 0001
  2. -1的补码：1111 1111

可以看到原码是被人脑直接识别并可进行计算的方式，那为什么还需要反码和补码呢？
这是因为对于人脑来说，可以一眼知道第一位是符号位, 在计算的时候我们不会对符号位进行计算，但是对于计算机, 加减乘数已经是最基础的运算,要设计的尽量简单. 计算机辨别"符号位"显然会让计算机的基础电路设计变得十分复杂，于是人们想出了将符号位也参与运算的方法. 我们知道, 根据运算法则减去一个正数等于加上一个负数, 即: 1-1 = 1 + (-1) = 0 , 所以机器可以只有加法而没有减法, 这样计算机运算的设计就更简单了。于是人们开始探索 将符号位参与运算, 并且只保留加法的方法. 首先来看原码:

计算十进制的表达式: 1-1=0

  1. 1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2

如果用原码表示, 让符号位也参与计算, 显然对于减法来说, 结果是不正确的。
这个时候反码出场了：

  1. 1 - 1 = 1 + (-1) =  [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0

发现没，如果使用反码运算，在真值部分的计算是正确的，但是多了一个符号位。让我们回过头来想想看，原码用最高位来标识一个数是正数还是负数，那0怎么办呢？实际上0有两种表示方式，+0和-0

  1. +0原码: 0000 0000
  2. +0反码：0000 0000
  3. +0补码：0000 0000
  5. -0原码：1000 0000
  6. -0反码：1111 1111
  7. -0反码：0000 0000

看到没，无论是+0还是-0补码都是一样的，所以用补码运算才能保证0的运算是正确的。回到1-1的场景：

  1. 1-1 = 1 + (-1) = [0000 0001]补 + [1111 1111]补 = [0000 0000]补 = [0000 0000]原 = 0

这样计算结果就正确了。所以计算机中数都是用补码表示的。

二、位运算种类及性质

2.1 异或

异或运算，相同为0，不同为1:
1 ^ 0 = 1;
1 ^ 1 = 0;
0 ^ 0 = 0;
根据异或的定义得到异或的一个重要性质，就是两个相同的数异或得0即n ^ n = 0，所以异或经常用来判定集合中是否有相同的数。
异或的另一个用途是交换两个数：

  1. a = a ^ b;
  2. b = a ^ b; // b = a ^ b ^ b = a
  3. a = a ^ b; // a = a ^ b ^ a = b

2.2 与运算

只有当两位都是1的时候与运算的结果才是1
1 & 1 = 1
1 & 0 = 0
0 & 0 = 0
与运算有一些重要的技巧：

2.2.1 判断数的奇偶

偶数的末位一定是0，而基数的末位一定是1，所以可以与1来得知一个数的奇偶：

  1. 偶数：X & 1 = 0
  2. 基数：X & 1 = 1

判断奇偶实际上是判断最右位是否为1，那如果要判断中间第n位怎么办呢？只要把1左移n位就可以了：

  1. x & (1<<n) == 1

2.2.2 消除高位，保留低位

这其实java中HashMap的经典hash算法，HashMap中需要将key映射到数组下标，但数组容量是有限的，要如何才能保证映射之后不会出现下标越界的情况呢？这就用到了与运算，实际上是：

  1. int index = hash & (length - 1)

这上面hash是key的hashcode处理过后的值，length是数组的容量，HashMap中数组容量总是2的n次方，这个数值减一之后的数值的二进制表示中高位都是0，低位都是1，HashMap默认容量是16，我们以16为例，16减1就是15，15的二进制表示如下：

  1. 15: 0000 1111

用这个数做与运算，不管hash有多大高位都会变成0，而低位会保持原有的数值，但是这个数值不管有多大都不会比各位都是1大，所以保证了这个数一定在数组范围内，实际上是消除了高位，保留了低位。

2.2.3 消除低位，保留高位

  1. x & (x - 1)

上面的运算每次可以消除最右的1而保留高位，原理也很简单，数值减1之后从某一位开始往右一定是各位都相反，这些位都可以消除。举例：

  1. 比如5 ：
  2. 5    ：0101 
  3. 5 - 1：0100
  4. 5 & 4：0100（消除了5最右位的1）
  5. 比如4：
  6. 4    ：0100
  7. 4 - 1：0011
  8. 4 & 3：0000（消除了4最右位的1）

一个经典的题目是统计一个数的二进制表示中有多少个1，那么用这个性质就能很轻松的得出答案：

  1. int count = 0;
  2. while (x != 0) {
  3.     x = x & (x - 1);
  4.     count++;
  5. }

2.2.4 保留最右位的1，其余位数置0

  1. x & (-x)

上面的运算即可保留x二进制表示中最右位的1，其余位数都置为1
比如6：

  1.  6的补码: 0000 0110
  2. -6的补码：1111 1010
  3. 6 & (-6)：0000 0010

2.3 或运算

两位中只要有一位是1或运算结果就是1，只有两位都是0或运算结果才是0
1 | 1 = 1
1 | 0 = 1
0 | 0 = 0

三、相关算法题

3.1 leetcode第645题 错误的集合

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

  1. 输入：nums = [1,2,2,4]
  2. 输出：[2,3]
  4. 输入：nums = [4, 2, 3, 2]
  5. 输出：[2, 1]

分析：
由于数组中只有一个重复的数，并且丢失了一个数，如果将集合和[1...n]构成一个大的集合，那么大的集合中正常的元素应该都是2个，重复的元素是3个，丢失的元素是1个，只有重复的元素和丢失的元素是奇数个，这时候整个大集合的元素做异或运算，最终的值将是重复元素和丢失元素异或的值，假设重复的元素为x，丢失的元素为y，那么整个集合异或的结果为x ^ y，记为r，r的二进制表示中从右往左第一个1的位置就是x和y二进制表示中的最低不同位，因为只有0和1异或才能得到1，问题是要如何计算得出这个位置，没错，需要用到与运算，用r与上-r就可以获取到r二进制中从右往左最低为1的位置，原因很简单，-r的二进制表示是r的补码（反码+1），r和-r的与运算刚好可以获取1的最低位，而且只有这一位是1，其他位都是0，举个例子，比如6：

  1.  6的补码: 0000 0110
  2. -6的补码：1111 1010
  3. 6 & (-6)：0000 0010

假设这个值为c = r & (-r)，那么用c和之前大集合中每一个元素进行与运算，如果结果为0表示这个元素在这个最低位是0，如果结果是c则代表这个元素在这个最低位为1，可以按照结果将大集合分为两个集合，而且重复的元素和丢失的元素一定分别被分到了两个集合中，对于其他元素来说只会存在在其中一个集合，所以这两个集合中其他元素都是偶数，其中一个集合中包含三个重复的元素，另一个集合包含一个丢失的元素，对这两个集合中的元素分别做异或运算，那么就可以获取到重复的元素和丢失的元素，但是我们还不知道这两个元素哪个是丢失的哪个是重复的，所以还要遍历一次元数组，看哪个元素在原数组中哪个元素就是重复的元素。

[4, 2, 3, 2]
和[1..4]组成大集合：[4, 2, 3, 2, 1, 2, 3, 4]
异或的结果为r = 3，二进制表示为0011
c = r & (-r) 即c = 1，二进制表示为0001
大集合中的元素与c做与运算，按结果分为两个集合：
[4, 2, 2, 2]和[3, 1, 3]
两个集合的元素分别做异或运算，得到2和1
但是还不知道2和1哪个是重复的哪个是丢失的，所以要到原集合中遍历，发现2出现在原集合中，就知道2是重复的，1是丢失的。

代码：

  1. public int[] findErrorNums(int[] nums) {
  2.     int n = nums.length;
  3.     int xor = 0;
  4.     for (int i = 1; i <= n; i++) {
  5.         xor ^= nums[i-1];
  6.         xor ^= i;
  7.     }
  8.     int lowbit = xor & (-xor);
  9.     int num1 = 0, num2 = 0;
  10.     for (int i = 1; i <= n; i++) {
  11.         if ((i & lowbit) == 0) {
  12.             num1 ^= i;
  13.         } else {
  14.             num2 ^= i;
  15.         }
  16.         int num = nums[i-1];
  17.         if ((num & lowbit) == 0) {
  18.             num1 ^= num;
  19.         } else {
  20.             num2 ^= num;
  21.         }
  22.     }
  23.     for (int num : nums) {
  24.         if (num == num1) {
  25.             return new int[]{num1, num2};
  26.         }
  27.     }
  28.     return new int[]{num2, num1};
  29. }

3.2 leetcode 231 2的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

2的幂次方的二进制表示有一个特点就是只有高位一个1，所以用n & (n-1)消除一个1之后是否为0即可判断.但是要注意边界情况，一个是0，一个是int的最小值
对于0，由于二进制表示中没有1，所以消除完还是0，但0本身是无法表示成2的幂次方的，而对于int最小值再减1就越界了，所以也要排除。

  1. public boolean isPowerOfTwo(int n) {
  2.     if (n == 0 || n == Integer.MIN_VALUE) {
  3.         return false;
  4.     }
  5.     return (n & (n - 1)) == 0;
  6. }

3.3 老鼠/兔子试毒（leetcode 458）

458原题如下：

  1. 有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。
  3. 喂猪的规则如下：
  5. 选择若干活猪进行喂养
  6. 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
  7. 小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
  8. 过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
  9. 重复这一过程，直到时间用完。
  10. 给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。
  12.  
  14. 示例 1：
  16. 输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60
  17. 输出：5
  18. 示例 2：
  20. 输入：buckets = 4, minutesToDie = 15, minutesToTest = 15
  21. 输出：2
  22. 示例 3：
  24. 输入：buckets = 4, minutesToDie = 15, minutesToTest = 30
  25. 输出：2

原题更加困难，我们先来看这个问题一个简单的变种：

  1. 有1000瓶药水，其中有一瓶是毒药，只要喝上一滴，15分钟之后就必死无疑。现在提供一批小猪来试毒，要怎么花最少的兔子、最少的时间，找出这瓶毒药呢？

这个变种的题目相当于原题目minutesToDie为15分钟，并且没有时间的限制，但是要求时间最少。很明显用1000只兔小猪，每只喂一瓶毒药，需要的时间是最少的，最少的时间就是15分钟。所以变种的题目可以改为：

  1. 用一天时间在1000瓶药水中用最少的小猪找出其中仅有一瓶的毒药水，小猪喝完毒药水之后要一天才能死亡。
  2. 相当于原题中buckets=1000，minutesToDie = 15, minutesToTest = 15

此时每只小猪都只能喝1次液体（再喝时间就不够了），每个小猪喝完若干瓶液体后只能出现两种状态，要么死亡，要么存活.

我们给这 1000 瓶液体分别标上一个唯一编号 0-999，由于 > 1000 > ，所以每瓶液体都对应着唯一的一个长度为10的二进制串. 我们只需要10只小猪，让每个小猪负责一个二进制位即可. 例如第一只小猪负责二进制串的最低位，那么它就需要喝掉所有二进制最低位为1的液体，如果这只小猪最后死亡，说明有毒液体的编号二进制最低位为1；否则小猪存活，有毒液体的编号二进制最低位为0. 这样一来，一只小猪就可以确定一个二进制位的取值，使用10只小猪就能完全确定有毒液体的编号.

现在回到原先的题目，考虑更为一般的情况：
假如buckets = 1000, minutesToDie = 15, minutesToTest = 60，此时每只小猪可以喝4次液体，在时间限制范围内，小猪可能出现的状态共有5种，分别为：喝完第1次后死亡、喝完第2次后死亡、喝完第3次后死亡、喝完第4次后死亡、喝完4次后依然存活. 现在每只小猪可以5种状态了，而不是之前的2种，那么我们就可以将瓶子的编号转换成五进制数考虑.

我们依然给这 1000 瓶液体分别标上一个唯一编号 0-999，由于 > 1000 > ，所以每瓶液体都对应着唯一的一个长度为5的五进制串. 我们只需要5只小猪，让每个小猪负责一个五进制位即可. 例如第一只小猪负责五进制串的最低位，那么它第一次先喝掉五进制最低位为1的液体，第二次先喝掉五进制最低位为2的液体，第三次先喝掉五进制最低位为3的液体，第四次先喝掉五进制最低位为4的液体. 在这一过程中，如果这只小猪某次喝完后死亡，就可以立马确定有毒液体五进制的最低位取值，如果喝完四次后仍存活，说明有毒液体五进制的最低位为0. 这样一来，一只小猪就可以确定一个五进制位的取值，使用5只小猪就能完全确定有毒液体的编号.

所以思路就是确定用几进制来表示状态，确定完之后在确定buckets用n进制表示至少需要多少位，这个位数就是答案。
先确定几进制：state = minutesToTest/minutesToDie + 1;
然后确定buckets用n进制表示至少需要多少位，用log运算即可，并且可以用换底公式进行转换：
logstatebuckets = logebuckets / logestate

所以最终的答案就是：

  1. public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
  2.     int state = minutesToTest / minutesToDie + 1;
  3.     return (int) Math.ceil(Math.log(buckets) / Math.log(state));
  4. }

四、参考文章

1、位运算： https://leetcode-cn.com/circle/article/VvijVQ/
1、算法笔记 - 位运算： https://leetcode-cn.com/circle/article/mDhWhf/

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注