bugCat's Blog

毛的感情的程序猿

0%

位运算题目小结

发表于 更新于 分类于
本文字数： 5.2k 阅读时长 ≈ 5 分钟

位运算题目小结

在刷Leetcode的时候发现许多位运算的题目，总结在一起看看能不能发现规律

78.子集

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

这题其实属于排列组合小结里面总结过的一题，不过这里面解释另外一种思路，通过位运算的思路来解决。但是其实本质上还是排列组合里面的选取和不选取的思想。

举例：假设nums=[1,2,3,4]，二进制的0可以写成0000，代表一个数也不取，1=0001表示去第一个数也就是[1]，2=0010，表示取第二个数[2]，3=0011表示取1和2位[1,2]，4=0100表示[3]….15=1111表示[1,2,3,4]

1
2
3
4
5
6
7
8
9
10
11
public  List<List<Integer>> binaryBit(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    for (int i = 0; i < (1 << nums.length); i++) {
        List<Integer> sub = new ArrayList<Integer>();
        for (int j = 0; j < nums.length; j++)
            //第i种情况取第j位的值，判断是不是1，是则选取
            if (((i >> j) & 1) == 1) sub.add(nums[j]);
        res.add(sub);
    }
    return res;
}

这个代码有个问题，就是nums.length超过32就处理不了，不过这个目前不用担心(因为如果超过长度超过32那用其他方法进行子集提取，估计也会非常消耗时间),这题的测试用例并没有超过32位

136.只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
输入: [2,2,1]
输出: 1

示例 2:

1
2
输入: [4,1,2,1,2]
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

这题做过很多次了，可以使用哈希表进行处理，但是最好的方法是使用异或^进行处理，这里利用到了异或的一个特性，两个相同的数异或为0（相同为0不同为1）

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res = res ^ nums[i];
        }
        return res;
    }
}

137.只出现一次的数字II

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
输入: [2,2,3,2]
输出: 3

示例 2:

1
2
输入: [0,1,0,1,0,1,99]
输出: 99

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

这次是一个元素出现一次，其他元素出现三次。这题可以使用哈希表进行处理，但是位了训练位运算，我们采取使用位运算的思想处理。

这题看了题解之后，我想到了计算机组成原理里面的真值表法，所以我们可以使用该方法进行处理。

首先我们想到需要一个逻辑运算实现 1*1*1=01∗1∗1=0 且 01=10=10∗1=1∗0=1 ，其中 *为这种新逻辑操作符。根据这个，我们可以想到

  • 出现0次为0，出现1次为1，出现2次的值无所谓，出现3次就又回到0，也就是说，我们一共需要记录3种状态：0次，1次，2次，之后次数都是这三种状态的循环。其实这也就是一个模三运算。

  • 记录两个状态需要的是一位二进制0/1，那么记录三种状态需要的是至少两位二进制，可以是00, 01, 10, 11，这里我们只需要选其中任意三个状态即可，例如：00，01，10，分别代表0次1次2次。

  • 用00代表0次，01代表出现1次是因为刚好对应数字原本那位上0代表0次，1代表1次，这样可以方便写程序，不这么选也可以，但最后你自己要有个映射规则。至于2次的编码无所谓，10和11都可以，反正最后答案也不要它，只是个中间状态，辅助我们计算的。

  • 那么对于输入数字的每一位二进制位，都可以用这三种状态表示。如果再输入一个数字，对于每一位上，我们的操作可以化为：

    • 新输入的是0（即00），三种状态都维持不变，00$\rightarrow $00,01$\rightarrow$01,10$\rightarrow$10

    • 新输入的是1（即01），00$\rightarrow$01,01$\rightarrow$10,10$\rightarrow$00

所以可以得出真值表

当前状态XY 输入Z 输出X 输出Y
00 0 0 0
01 0 0 1
10 0 1 0
00 1 0 1
01 1 1 0
10 1 0 0

XY是指两位数表示的状态，因为1位只能表示2个状态。后面的XY表式输出后的状态，其实6个状态对应着前来说的输入为0和输入为1，比如第一行其实就是00*0$\rightarrow $00

根据真值表的求法这里，可以得到

然后我们可以根据布尔表达式化简一下

同理可得

所以答案可以是这样y

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    
    public int singleNumber(int[] nums) {
        int y = 0, x = 0;
        for (int z : nums) {
            int _y = y;
            y = ~x & (y ^ z);
            x = x&(~_y)&(~z)|(~x)&(_y)&(z);
        }
        return y;
    }
}

标准答案是这样，应该是最终化简后的结果

1
2
3
4
5
6
7
8
9
10
class Solution {
    int seenOnce = 0, seenTwice = 0;
    public int singleNumber(int[] nums) {
        for (int num : nums) {
            seenOnce = ~seenTwice & (seenOnce ^ num);
            seenTwice = ~seenOnce & (seenTwice ^ num);
        }
        return seenOnce;
    }
}

思考：最终为啥返回y而不是返回x

因为最终返回的是出现次数1次的数字，只有Y为1的时候才代表该数出现一次

191.位数1的个数

题目描述

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：

1
2
3
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

1
2
3
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

1
2
3
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

  • 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
  • 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-1-bits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

方法思路比较简单，就是n&(n-1)

1
2
3
n   = 0010
n-1 = 0001
n&(n-1) = 0000

这样就取出了末尾的1

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

201.数字范围按位与

题目描述

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1: 

1
2
输入: [5,7]
输出: 4

示例 2:

1
2
输入: [0,1]
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

参考标准答案：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/solution/shu-zi-fan-wei-an-wei-yu-by-leetcode/

其实就是找n和m的公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
  public int rangeBitwiseAnd(int m, int n) {
    int shift = 0;
    // find the common 1-bits
    while (m < n) {
      m >>= 1;
      n >>= 1;
      ++shift;
    }
    return m << shift;
  }
}

利用n&(n-1)

1
2
3
4
5
6
7
8
9
class Solution {
  public int rangeBitwiseAnd(int m, int n) {
    while (m < n) {
      // turn off rightmost 1-bit
      n = n & (n - 1);
    }
    return n;
  }
}

总结

总结一些位运算可能使用到的规律：

  • 两个相同的数异或值为0，用于筛选出独特的数，eg：136.只出现一次的数字
  • 有时候可以使用真值表法
  • 使用n&(n-1)取出末尾的1