跳转至

位运算

位运算优先级：位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符

典型应用：

位取反运算符

~的作用是对数字n的二进制表示进行按位取反，如果n是非负整数（也就是自然数），则~n = -1 * (n + 1)，也就是~0=-1, ~5=-6。如果n是负数，则~n = -1 * n - 1，也就是~5 = 4。

正数的补码是其原码，负数的补码是其绝对值 按位取反后加一，符号位（即第一位）不变。

非负数的表示是其原码，负数用其相反数的补码表示。所以读到一个二进制数其最高位为1，则先去掉最高位，剩余的二进制表示减1然后按位取反得到数字，然后加上符号。 $$ \sim n = -(n+1), \quad n \geq 0\ \sim n = -n - 1, \quad n < 0\ \therefore \sim n = -n-1\ $$

计算乘2的非负整数次幂

n \times (2^m) = n << m

假设数字n表示成二进制有k-1位（从0开始计数），则数字可以被表示成： $$ n = b_{k-1}2{k-1}+b_{k-2}2{k-2}+\cdots +b_0\ b_i = 0 或1,其中0 \leq i \leq k-1 \ n \times (2^m) = (b_{k-1}2{k-1}+b_{k-2}2{k-2}+\cdots +b_0) \times 2^m \ = (b_{k-1 }2{k-1+m}+b_{k-2}2{k-2+m}+\cdots +b_02^m) $$ 从表达式可以看出，相当于数字n右移m位，所以上式相等。

除以2的非负整数次幂

\frac{n}{2^m} = n >> m

证明方法同上。

判断一个数是不是2的正整数次幂

  • LeetCode 231.2的幂
bool isPowerOfTwo(int n) 
{ 
    return n && !(n & (n - 1)); 
}

证明：2的正整数次幂首先这个数n必须是正整数，如果是2的正整数次幂，那么其二进制表示就是10000\cdots 000，n-1的二进制表示就会成为0111\cdots 1111，所以进行与运算结果为零。

对2的非负整数次幂取模

这里mod是2的非负整数次幂值，如1，2，4，8，16，x是一个非负整数。求x % mod的值。特殊的，当mod = 2时退化成x & 1，和判断奇偶数的形式一样了。

int modPowerOfTwo(int x, int mod) 
{ 
    return x & (mod - 1); 
}

证明：设mod = 2^m，将数字x表示成二进制： $$ x = b_{k-1}2{k-1}+b_{k-2}2{k-2}+\cdots +b_0\ x / mod = x >> m \ = (b_{k-1}2{k-1}+b_{k-2}2{k-2}+\cdots +b_0) / 2^m \ = (b_{k-1}2{k-1}+b_{k-2}2{k-2}+\cdots +b_m2^m + b_{m-1}2^{m-1} + \cdots+b_0) / 2^m \ =\frac{b_{k-1}2{k-1}+b_{k-2}2{k-2}+\cdots +b_m2m}{2m} + \frac{b_{m-1}2^{m-1} + \cdots+b_0}{2^m} \ $$ 前半部分就是商，也就是右移m位后留下来的部分，那么左半部分因为指数小于2^m，所以后面的位组成的十进制数肯定小于mod也就是2^m。意味着b_{m-1}2^{m-1} +\cdots+b_0就是余数，也就是要取出原数字x的后m位，mod转成二进制就是10000\cdots000，那么只需要减1再进行与运算即可。

计算绝对值

#include <climits> //CHAR_BIT在此头文件定义，包括INT_MAX和INT_MIN等常量
int ABS(int n)
{
    const int mask = n >> (sizeof(int) * CHAR_BIT - 1);
    return (n ^ mask) - mask;
}

这里第一步计算mask是为了取出数字n的最高位来判断符号。如果n是自然数，则mask为0，则n^0 = n，所以(n ^ mask) - mask = n。括号是不能少的，因为减法运算（算术运算）的优先级要高于位运算。

如果n是负数，则mask=-1，则n ^ mask需要计算n和-1的补码然后进行按位异或。-1的补码各个二进制位全是1，n的补码与之异或相当于全部二进制位按位取反，得到的是-n - 1，所以结果是-n - 1 - (-1) = -n得到的就是绝对值。

计算两数中的较大值和较小值

#include <climits>
int r;
r = y ^ ((x ^ y) & -(x < y)); //min(x, y)
r = x ^ ((x ^ y) & -(x < y)); //max(x, y)
// If we know INT_MIN <= x - y <= INT_MAX, the following is much faster
r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); //min(x, y)
r = x + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); //max(x, y)

假如x < y，那么-(x < y) = -1，刚才已经分析了-1的补码各个二进制位都是1，所以(x^y) & (-1) = x ^y，那么r = y ^ (x ^ y) = x = min(x, y)，对于max(x, y)的分析同理。

如果x > y，那么-(x < y) = 0，则(x^y) & 0= 0， 那么y ^ 0 = y即为min(x, y)。

建议采用第一种方案，第二种虽然速度快但是多了限制条件，很容易在不察觉的情况下引发bug。

判断两个数符号是否相同

#include <climits>
bool isSameSign(int a, int b)
{
    if (!a || !b) return false;//0的特殊情况要单独判断

    return (x ^ y) >= 0; 
}

另一种方法：

#include <climits>
bool isSameSign(int a, int b)
{
    return !((a >> 31) ^ (b >> 31)); //判断最高位即可
}

交换两个数

void Swap(int & a, int & b)
{
    return a ^= b ^= a ^= b;
}

上面的代码拆解开来： $$ a = a \land b \ b = b \land a = b \land a \land b = a \ a = a \land b = a \land b \land b \land a \land b = b \ $$ 于是在不使用中间变量的情况下完成两数的交换。

数字越界判断

比如判断0 <= a && a <= INT_MAX需要进行两次判断，可以用位运算修改为无分支的情况：

#include <climits>

统计数字n的二进制位中1的个数（汉明重量）

统计二进制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，则我们可以通过下面方法去统计：
int cnt = 0; 
while(a){  
    a = a & (a - 1);  
    ++cnt;  
}

计算带符号整数的最大值和最小值

也就是计算包含在头文件<climits>里的INT_MIN和INT_MAX，其中一种写法是直接定义：

const int INF = 0x0ffffff;

经过测试，这种写法其实并不能取到正整数的最大值，比如：

#include <iostream>
#include <climits>

using namespace std;

int main()
{

    const int INF = 0x0ffffff; 
    cout << INF << endl;
    cout << INT_MAX << endl;

    return 0;
}

# result
16777215
2147483647

发现两者并不相同，INF < INT_MAX。另外的方法就是自己写一个函数来计算出INT_MIN和INT_MAX:

#include <iostream>
#include <climits>

using namespace std;

int getMax()
{
    int mask = (sizeof(int) * CHAR_BIT) - 1;
    return ~(1 << mask); //也可以写为(1 << mask) - 1
}

int getMin()
{
    int mask = (sizeof(int) * CHAR_BIT) - 1;
    return 1 << mask;
}

int main()
{
    cout << INT_MAX << endl;
    cout << getMax() << endl;
    cout << getMin() << endl;
    cout << INT_MIN << endl;

    return 0;
}

# result
2147483647
2147483647
-2147483648
-2147483648

原理是先计算出对于一台计算机是用多少位来表示int的，因为不同位数的计算机可能有所不同，所以保险起见还是用int mask = (sizeof(int) * CHAR_BIT) - 1;，然后将数字1移动到最高位，那么最高位是1，后面的所有位都是0，然后按位取反，则最高位是0，剩余的位全是1，显然就是INT_MAX。

计算INT_MIN是直接1 << mask，也就是最高位是1，剩余位全是0.最高位为1代表着这个数是负数，那么它实际表示的数是除了最高位以外其余位按位取反得到的是INT_MAX，然后这个数减1，加上负号，所以表达的是INT_MIN。

计算两个数的中间值

这个在二分法里面经常用到，两个数字a, b，如果直接计算(a+b)/2可能存在数据溢出，那么保险的方法是

int mid = a + ((b - a) >> 1); //也就是a + (b - a) / 2

如果转化成用位运算表示：

int mid = (a & b) + ((a ^ b) >> 1);

原理分析的参考：https://blog.csdn.net/QQ1910084514/article/details/80092380

考虑两个数的二进制表示，相加也就是对应的采用指数表示的二进制位相加，即： $$ a = a_{k-1} 2^{k-1} + \cdots + a_0 \ b= b_{k-1} 2^{k-1} + \cdots + b_0 \ 对应位相加：(a_i + b_i)2^i $$ 那么如果对应位同为1，则表示成2\times2^i，一个为0一个为1则是1\times2^i，所以a+b可以表示成 $$ a +b = (2 \times (a \& b)) + ( a\land b)\ \therefore (a+b) / 2 = (a \& b) + ((a \land b) >> 1)\ $$

集合的整数表示

来源于《挑战程序设计竞赛》“反转”章节。将集合用整数表示，便于操作还能加快运算速度。

对于整数集合S = {0,1,2,...,n-1}，可以用一个整数来表示，其实本质就是每个数字对应于一个二进制位，所以有f(S) = \sum_{i\in S} 2^i

于是有以下一些常用技巧：

  • 空集
0
  • 只含有第i个（从下标0开始计数）元素
1 << i
  • 含有集合S的全部元素的表示，相当于求\sum_{i = 0}^{n - 1}2^i = 2^n - 1。注意位运算优先级低于算术运算，所以要加括号。
(1 << n) - 1
  • 判断第i个（下标从0开始计数）元素是否属于集合，相当于检验i对应的二进制位是否为1
if (S >> i & 1)
  • 向集合中加入第i个元素，相当于将i对应的二进制位变为1
S | (1 << i)
  • 从集合中除去第i个元素，相当于将i对应的二进制位变为0
S & ~(1 << i)
  • 集合S和集合T的并集
S | T
  • 集合S和集合T的交集
S & T
  • 将集合{0,1,2,...,n-1}全部列举出来，将会按照0，1，01，……，{0,1,2,...,n-1}的顺序枚举出来
for (int s = 0; s < (1 << n); ++s) {
    //对集合S的操作
}
  • 特殊集合的子集的枚举，比如由0，2，4等组成的集合表示成二进制是0....10101，也就是对应的二进制位为1，那么类似这样的集合的子集去枚举
int sub = s;
do {
    /*
    {对子集的处理操作}
    */
    sub = (sub - 1) & s; //寻找下一个子集
} while (sub != s); //所有子集枚举完成后sub = -1，-1 & s = s，退出循环

比如只含0，2，4的集合，按照上面的方法，会按照下面的顺序进行枚举：

4 2 0
4   0
4
  2 0
  2
    0
  • 枚举集合{0,1,2,...,n-1}的所有长度为k的集合。
int s = (1 << k) - 1;
while (s < (1 << n)) {
    /*
      {针对长度为k的集合的处理}
    */
    int x = s & -s; //取出最后一个1
    int t = s + x; //将最后连续的1最左边的1往左移动1位
    s = (((s ^ t) / x) >> 2) | t;
}

参考了《挑战程序设计竞赛》和这篇博客

与这道题相关联的变形可以是POJ 2453，给定一个**正整数**N，求最小的、比N大的**正整数**M，使得M与N的二进制表示中有相同数目的1。基本上是同一种方法，两者的本质都是给定一个已知满足条件的数字，然后去寻找“紧邻”的比当前大的下一个数字。

以N=78为例(其二进制表示为1001110)，我们的任务是求得最小的比N大，二进制表示中1的个数与N相同的数：83(其二进制表示为1010011)。首先我们要总结出来从78变成83的规律，为了方便，将78和83的二进制写成竖式形式：

78：1 0 0 1 1 1 0

83：1 0 1 0 0 1 1

可以看出，为了得到83，我们只需要对N(78)的二进制中最右边的连续的1位串(加粗标红)进行操作！其过程是：将连续的1位串中最左边的1向左“移动”一位，其他的1位串“移动”到最右边！这即保证了二进制表示中1的个数不变，又保证了新得到的数比原来的数大，并且是最小的。

在上面的描述中我用引号把两个“移动”引起来了，原因是，具体实现时，我们并不是对这些二进制位进行移动，而是通过位操作来达到同样的目的，而这些位操作就是本问题的关键。接下来我将分析前面那个“非常给力的代码”看看它是如何用位操作来实现对这些位的“移动”的。

首先来看语句**int x = N&(-N);**它的功能是找到N(即78)的二进制表示中最右边的1(这个1必定是N的二进制表示中最右边的连续的1位串的开始)。该过程图示如下：

1581832154727

接下来看看**int t = N+x;**该语句实现了“**将连续的1位串中最左边的1向左“移动”一位”**的功能，当然它带来了副作用：使得连续的1位串中其他的1丢失了！其过程如下：

1581832177383

最后的任务就是要将上面丢失的1补上，并放到最右边，这就是语句int ans = t | ((N^ t)/x)>>2;的功能。首先，要知道需要补多少个1，通过分析可以知道需要补上的1的个数等于N的二进制表示中最右边的连续的1位串中1的个数减1，然而如果通过位操作来求得呢？这就是N^ t的功能了，如下图所示，N^t的二进制表示只包含1个连续的1串，并且1的个数正好等于N的二进制表示中最右边的连续的1位串中1的个数加1：

1581832226294

由上面的分析可知，N^ t中的1的个数实际上比我们需要补的1的个数多2！这就使得我们可以通过N^t求得需要补的1的个数，接下来的任务就是如何补上这些1了。

进步一分析得知，N^ t的二进制表示中最低位的1正好与x中那个1对应，因此我们就可以通过(N^ t)/x将这些1全部移到最右边了，然而此时1的个数比我们要补的个数多了2，没关系我们在把结果右移2位就可以了，也就是((N^t)/x)>>2。如此一来我们求得了要补的1的个数和其位置。本段的描述可以用下图形象地表示：

1581832267226

最后我们只需要用**t | ((N^t)/x)>>2;就能得到所求之数了！其过程如下图：**

1581832291399

另外，对于《挑战程序设计竞赛》书中提到的不包含相邻元素的集合的枚举，在这篇博客里给出了扩充的解答。

建议这个部分单独拿出来，仍然属于“位运算”专题

位运算解决n皇后问题

Matrix67的第三篇关于二进制的博客。

数字范围按位与

  • LeetCode 201 数字范围按位与

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

示例 1: 

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

将5，6，7的二进制写出：

5 101
6 110
7 111
5 \& 6 \& 7 = 100_2 = 4

思路是去寻找左右边界从右向左第一个不同的位置，最后保留相同的部分即可。因为范围从m到n是连续的，那么它们的公共前缀部分设为xxx，则第一个不相同的位置肯定在n是1， 在m里是0，不然违背大小关系。那么从m增长到n，则首先需要增长到xxx0111..11，然后增长到xxx100...00，然后再增长到n，那么很显然xxx0111..11和xxx100...00按位与，xxx后面的肯定都是0，那么也就意味着只需要求出m和n的相同二进制前缀即可。

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        unsigned int mask = INT_MAX;
        while ((m & mask) != (n & mask)) {
            mask <<= 1;
        }

        return mask & m;
    }
};

数字的补数

  • LeetCode 476 数字的补数
  • LeetCode 1009 数字的补数（两个题一模一样）

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

示例 1:

输入: 5
输出: 2
解释: 5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

class Solution {
public:
    int findComplement(int num) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        unsigned int mask = INT_MAX;
        while (mask & num) mask <<= 1;

        return (~num) & (~mask);
    }
};

按位取反很自然的联想到运算符~，但是如果能够固定数量的按位取反，其实可以考虑利用INT_MAX的移位操作，不断左移，直到和num的与运算为0，那么就可以确定需要按位取反的有多少位了，注意输入都是正整数，所以不存在输入为0的情形。另外要用unsigned int类型。

典型题目

出现在《C++程序设计思想与方法》的辅导书里第一章，《C++primer》里的位运算基本知识讲解。

异或运算相关：https://www.cnblogs.com/encodetalker/p/10700434.html

集大成者：https://graphics.stanford.edu/~seander/bithacks.html

leetcode总结：https://blog.csdn.net/EbowTang/article/details/51228929

可以参考：https://www.cnblogs.com/thrillerz/p/4530108.html

https://www.zhihu.com/question/38206659?sort=created

以及Matrix67位运算系列的基础+进阶1+进阶2+实战篇https://blog.csdn.net/wangs915/article/details/8735774

https://blog.csdn.net/leelitian3/article/details/80251902

很不错的总结：

C/C++刁钻问题各个击破之位运算及其应用实例(1) 里面还是存在一些问题，不过其交换数字的第一种方法还是很新奇的。

c_c++刁钻问题各个击破之位运算及其实例(2)

给力！高效！易懂！位运算求组合

给力！简单！易懂！位运算之求集合的所有子集

  • LeetCode 136 Single Number
  • LeetCode 137 Single Number 2
  • LeetCode 260 Single Number 3
  • LeetCode 201 数字范围按位与
  • LeetCode 476 数字的补数
  • POJ 3748 位操作
  • POJ 2309
  • POJ 3690
  • POJ 3220
  • POJ 2453（位运算计算二进制1个数相同的下一个数）
  • POJ 1222
  • POJ 1753 （位运算 + BFS）
  • POJ 3279
  • HDU 5969
  • HDU 5344
  • HDU 3257
  • HDU 1390
  • HDU 5747
  • HDU 3935
  • HDU 4321
  • HDU 3782
  • HDU 4825 字典树 + 位运算
  • Google Kick Start 2019 Round G（异或运算）