位运算

Posted on | In ,

本文将针对位运算进行总结。

常用位运算总结

位运算优先级

位运算的优先级是很低的，所以在使用的时候在必要时要加括号。例如if((v & h) == 0)，如果不加括号，会变成判断h是否为0。

异或运算^

异或的一些基本性质如下：

  • a^b，相异为1，相同为0
  • a^a = 0
  • a^0 = a
  • 满足交换律a\^b\^a = a\^a\^b = b

异或运算的常见应用场景

一、消除重复

因为a\^b\^a = a\^a\^b，故一些情况下，我们可以利用位运算，实现重复数的消除，获得只出现一次的数字

二、计算绝对值

面试题 16.07. 最大数值

不使用比较运算的情况下，获得一个数的绝对值

max(a, b) = ((a + b) + abs(a - b)) / 2

这里直接给出结论，以int为例：分析运算：(num ^ (num >> 31)) - (num >> 31)

  • num >= 0: num >> 31 => 0，即：(num ^ 0) - 0，结果为var

  • num < 0: num >> 31 => 0xFFFFFFFF，即：(num ^ 0xFFFFFFFF) - 0xFFFFFFFF，num ^ 0xFFFFFFFF是在对num 的全部位取反，-0xFFFFFFFF<=> +1, 对signed int取反加一就是取其相反数。

三、交换变量

为了交换整型变量a和b，我们可以进行如下三步操作：

  • a=a^b;

  • b=a^b;

  • a=a^b;

解释如下：令 a‘=a^b; 那么 b=a’^b = (a\^b)\^b=a\^b\^b=a\^(b\^b)=a^0=a，而 a’ = a^b = (a\^b)\^a=a\^b\^a=b。

例题

LeetCode 136 只出现一次的数字

一个数组中其他数字都出现两次，只有一个数字出现一次，找到这个数，只需进行一次全员异或即可。

LeetCode 260 只出现一次的数字3

一个数组中其他数字都出现两次，只有两个数字出现一次，找到这两个数。

思路

进行全员异或，能够找到这两个数字异或的结果，其他数字异或后全部为0，那么如何区分这两个数字呢？如果两个数字不同，那么异或之后一定至少有1位是1，我们可以以该位是否为0，将所有数字分为两组，这样问题就转化为了136题。

代码

LeetCode 371. 两整数之和
LeetCode 1009. 十进制整数的反码

计算十进制非负整数N的反码的过程如下，首先判断N有多少位为1，然后按位取反

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
class Solution {
public:
    int bitwiseComplement(int N) {
        if(N == 0) return 1;
        unsigned int flag = 1;
        int bit_num = bitCount(N);
        
        while(bit_num > 0){
            if((flag & N) != 0){
                bit_num--;
            }
            N ^= flag;
            flag <<= 1;
        }

        return N;
    }
    
    int bitCount(int N){
        if(N == 1) return 1;
        else if(N == 0) return 0;
        else if(N & 1 == 1) return 1 + bitCount(N >> 1);
        else return bitCount(N >> 1);
    }
};

按位与运算&

获取1的个数

对于任意数字 $n$ ，将 $n$和$n-1$做与运算，会把最后一个 1 的位变成 0。在二进制表示中，数字$n$中最低位的1总是对应$n-1$中的0。因此，将$n$和$n-1$与运算总是能把$n$中最低位的1变成0，并保持其他位不变。

1
2
3
4
5
6
7
8
int getNumsOfOne(int n){
    int count = 0;
    while(n){
        count++;  //只要n不为0则其至少有一个1
        n = n & (n - 1);
    }
    return count;
}

移位运算>> <<

用移位实现乘除法

移位运算可以用于乘除法当中，设乘数或除数$x=2^n$，则

  • $a\times x=(a<<n)$
  • $a/x=(a>>n)$

掩码操作

使用掩码对集合进行表示

在一些情况下，我们需要计算两个集合是否具有相同元素，例如两个字符串是否有相同字符。除了使用哈希方法外，我们还可以用位掩码进行操作。我们选择一个32位无符号整数，从1到第26位，分别记为a-z的标记，计算两个字符的掩码。如果掩码相与为0，那么两个字符串无相同的字符。

318. 最大单词长度乘积

有时我们需要获得一个集合的子集，那么我们可以采用掩码的方式进行，例如对于集合[1,2,3]，我们给定掩码[0,1,1]，0代表选择，1代表不选择，那么掩码[0,1,1]代表集合[2,3]。相关例题如下：

面试题 08.04. 幂集

卡诺图

在考虑状态转移时，经常会使用卡诺图作为工具，我们可以以当前状态和下一时刻状态做出2维卡诺图，从而进行判断。这里以LeetCode289. 生命游戏为例，对卡诺图的使用进行总结。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

  • 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
  • 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
  • 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
  • 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

细胞的状态有两种，死或活，根据当前状态并结合生存定律，可以推算下一状态，得到卡诺图如下：

下一状态\ 当前状态 死 活
死 00 01
活 10 11

每个细胞整型数可以保存其当前状态和下一状态，通过掩码进行实现。

一些例子1

比较复杂的位运算组合

下面这个例子揭示了位运算的一些技巧：

1
2
3
4
5
/* getbits: get n bits from position p*/
// 从x的第p位（p>=0）开始，获得n位
unsigned getbits(unsigned x, int p, int n){
    return (x >> (p+1-n)) & ~(~0 << n);   
}

练习

  1. 写出一个

参考文献

0%