前言

位运算就是和加减乘除等算术运算一样基础的逻辑运算，包括与或非，异或和移位。虽然非常基础，不过在日常的变成中使用的场景却不多，主要是技巧性太强，而且可读性差。即使在汇编编程中，位运算使用场景比较广的也是接口编程等比较专业的地方。但是，在底层编程，标准库等场景中，位运算还是有着不小的应用场景。另外在状态压缩，大数处理，甚至面试中，也少不了它的声音。故位运算还是值得我们去学习的，这篇文章就是我学习位运算以及刷题的一些记录。

常见应用

浮点数不能位运算

基本

基本操作原则

等价：

a=b^c

b=a^c

c=a^b

0^0=0

0^1=1

1^0=1

1^1=0

x^y=y^x

(x^y)^z=x^(y^z)

0^x=x

1^x=~x

x^x=0

位查询与修改

获取某位

// 获取 x 的第 pos 位
int getBit(int x,int pos) {
	return (x>>pos)&1;
}

// 获取从 pos 开始的 cnt 位
// 原理也是先右移 pos 位，找到起始点，然后取 cnt 位，就是把和一个数相与，即 cnt 个 1，
// 32-cnt 个数的0，这个数用 (1<<cnt)-1 得出，即先左移 cnt 位，如 1000000，再减一就是
// 0111111
int getBits(int x,int pos,int cnt) {
	return (x>>pos)&((1<<cnt) -1));
}

可以看出来，与的作用主要就是清零，然后取某些位的作用。而与的数就是 mask 掩码。

某位置 1

// 将 x 的第 pos 位设置为 1
int setBit(int x,int pox) {
	return x | (1<<pos);
}

设置 1 也很简单，就是对应位与 1 相与即可。可以看出来，或运算的主要功能就是置 1.

某位清零

// 将 x 的第 pos 位设置为 0
int unsetBit(int x,int pos) {
	return x & ~(1<<pos);
}

设置 0 和设置 1相反，置1用或运算，而清零则用与运算，并且掩码也不一样。置1是 000100 这样只有一个1，而清零则是 11110111 这样只有一个 0.

掩码直接移位取反即可。

某位取反

// 将 x 的第 pox 位取反
int flapBit(int x,int pox) {
	return x ^ (1 << pox);
}

取反特定位则与清零和置一不同，用到的是异或.由于 x^0=x,x^1=~x。故我们只要掩码设为 00001000，和置 1 类似，只是变成相异或，就能设置 1 的对应位取反。

找到最低位的 1

x&(-x)=x&(~x+1). 1会和最低的 1 开始一直进位，知道为 0.最后结果就是最低位 1 的位置。而其他则会被清零。

int lowbit(int x){
	return x&(-x);
}

消除最后一个 1

和找到最低位 1 类似

int clear(int x){
	return x&(x-1);
}

数学性质

判断两数是否异号

即判断两个是是否都是正数或是负数，或者一负一正。原理很简单，最高位异或，然后看最高位是不是 1，即结果是不是小于 0 即可。

bool isOppositeSign(int x,int y){
	return (x^y)<0;
}

判断奇偶

最后一位是 0 还是 1，因此就是取某一位判断。

bool isEven(int x){
	return (x&1)==0;
}

交换两数

异或的基本原理，面试的时候比较常见，不过真正使用频率并不高。

void swap(int x,int y){
	x^=y;
	y^=x;
	x^=y;
}

自增、自减

原理就是 - 的底层操作，- 的原理就是取反加一，故 -(~a) 就是 ~(~a)+1=a+1. (-a)=(~a+1)=a-1.

int inc(int x){
	return -(~x);
}
    
int dec(int x){
	return ~(-y);
}

判断是否是 2 的指数

如果是 2 的指数，如 2，4，8 ，那么就必然只有一个 1.如 0001，0010，0100.那么我们清空最低位 1，再判断是否为 0 即可。

bool isTowExponent(int n) {
	return (n&(n-1))==0;
}

求相反数

求补，取反+1

int reverseSign(int n) {
	return (~n)+1;
}

求绝对值

判断正负

int abs(int n) {
	int s=(n>>31);
	return (s==0)?n:(~n+1);		
}

// 优化
int abs(int n) {
	int s=(n>>31);
	return (n^s)-s;
}

位数逆转

循环移位

c++ 没有循环移位功能，不过可以使用移位和或运算模拟，如向右循环移位 n 位

int ror(int x,int n) {
	x=(x>>n)|(x<<(32-n));
}

int rol(int x,int n) {
	x=(x<<n)|(x>>(32-n));
}

高低位交换

int 32 位，高低 16 位交换位置，就是左移 16 位，右移 16 位，然后两者相与

int reverseLH(int n) {
	return (n << 16) | (n >> 16);
}

二进制逆转

取 a 的奇数位并用 0 进行填充可以表示为：a & 0xAAAA 取 a 的偶数为并用 0 进行填充可以表示为：a & 0x5555 因此，上面的第一步可以表示为：a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)

int reverseInt(int n) {
	n = ((n & 0xAAAA) >> 1) | ((n & 0x5555) << 1);
	n = ((n & 0xCCCC) >> 2) | ((n & 0x3333) << 2);
	n = ((n & 0xF0F0) >> 4) | ((n & 0x0F0F) << 4);
	n = ((n & 0xFF00) >> 8) | ((n & 0x00FF) << 8);
	return n;
}

集合操作

模拟集合操作

每一位表示一个数字，1 表示在集合中，0 表示不在集合中。

其它

大小写转换

根据字符 ASCII 码之间的关系

// 转换为大写
char toUpper(char c){
	return c&'_';
}

// 转换为小写
char toLower(char c){
	return c|' ';
}

// 大小写相互转换
char exchage(char c){
	return c^'c';
}

求 1 的个数

求 1 的个数就是求各位的和

int bitCount_3(u32 x) {
    x-= ((x & 0xAAAAAAAAu) >> 1);
    x = ((x & 0xCCCCCCCCu) >> 2) + (x & 0x33333333u);
    x = ((x >> 4) + x) & 0x0F0F0F0Fu;
    x = (x * 0x01010101u) >> 24;
    return x;
}

求前缀、后缀 1 的个数

int countLeadingZeros_1(u32 x) {
    int ans = 0;
    if (x >> 16) x >>= 16; else ans |= 16;
    if (x >> 8) x >>= 8; else ans |= 8;
    if (x >> 4) x >>= 4; else ans |= 4;
    if (x >> 2) x >>= 2; else ans |= 2;
    if (x >> 1) x >>= 1; else ans |= 1;
    return ans + !x;;
}

int countTrailingZeros_1(u32 x) {
    int ans = 0;
    if (!(x & 65535u)) x >>= 16, ans |= 16;
    if (!(x & 255u )) x >>= 8, ans |= 8;
    if (!(x & 15u )) x >>= 4, ans |= 4;
    if (!(x & 3u )) x >>= 2, ans |= 2;
    if (!(x & 1u )) x >>= 1, ans |= 1;
    return ans + !x;
}

实现三目表达式

我们可以利用表达式 y ^ ((x ^ y) & -cond) 来实现选择的功能:

若 cond = 1，其结果为 x

若 cond = 0，其结果为 y

int branch(bool cond,int x,int y){
	return y ^ ((x ^ y) & -cond);
}

0 和 1 转换

0 即 00000000，1 即 000000001，

0^1=000000000^000000001=000000001=1

1^1=000000001^000000001=000000000=0

int exchage(int n){
	return n^1;
}

构造低位全 1 的掩码

如 5 即 0101 → 000000ffh

int getMask(int x){
	x|=x>>1;
	x|=x>>2;
	x|=x>>4;
	x|=x>>8;
	x|=x>>16;	
	return x;
}

题型

编码性质

编码性质是指使用位运算处理一些编码上的问题，比如数的表示，循环码，字符编码等等。

• list

  476. 数字的补数

  题意

  将数低位取反

  分析

  最简单的自然是从左边遍历，找到第一个 1，然后开始取反，就是个简单的获取设置位操作。

  优化

  要取反的话，其实和 1 异或就是，0^1=1,1^1=0.故我们只要构造掩码，即低位全 1，然后异或即可。

  效率

  时间复杂度：$O(n)$，掩码是 $O(1)$

  空间复杂度：$O(1)$

  代码

  遍历模拟

  class Solution {
  public:
      int findComplement(int num) {
          int cnt=0;
          bool flag=false;
          
          for (int i=31;i>-1;i--){
              int b=getBit(num,i);
                  
              if (b==0 && !flag) {
                  continue;
              }
              if (b==1 && !flag){
                  flag=true;
              }
              
              num=flapBit(num,i);
          }
          
          return num;
      }
      
      int setBit(int x,int pos){
          return x|(1<<pos);
      }
      
      int unsetBit(int x,int pos){
          return x&(~(1<<pos));
      }
      
      int getBit(int x,int pos) {
          return (x>>pos)&1;
      }
      
      int flapBit(int x,int pos){
          return x^(1<<pos);
      }
  };

  掩码异或（取反）

  class Solution {
  public:
      int findComplement(int num) {
          return getMask(num)^num;
      }
      
      int getMask(int x){
  	    x|=x>>1;
  	    x|=x>>2;
  	    x|=x>>4;
  	    x|=x>>8;
  	    x|=x>>16;	
  	    return x;
      }
  };

  1009. 十进制整数的反码

  同 476.

  打印补码的最值

  题意

  打印补码的最值（范围）

  分析

  这是 csapp 的一个 lab，有助于我们理解补码的性质。

  10000000 00000000 00000000 00000000 → INT_MIN 即 $-2^{31}=-2147483648$

  00000000 00000000 00000000 00000000 → 0

  01111111 11111111 11111111 11111111 → INT_MAX 即 $2^{31}-1=2147483647$

  void show range() {
  	cout << (~(1<<31))<<endl;
  	out << 0 <<endl;
  	cout << (1<<31)<<endl;
  }
  
  void showAll() {
  	cout << bitset<32> (INT_MIN) << endl;
  	cout << bitset<32> (-1) << endl;
  	cout << bitset<32> (0) << endl;
  	out << bitset<32> (1) << endl;
    cout << bitset<32> (INT_MAX) << endl;
  }
  
  10000000000000000000000000000000
  11111111111111111111111111111111
  00000000000000000000000000000000
  00000000000000000000000000000001
  01111111111111111111111111111111

  89. 格雷编码

  题意

  生成格雷编码

  分析

  使用数电中生成格雷编码的算法，n 位到 n+1 的过程是：

  1. 先镜像对称增加原数组
  2. 再把新增加的数高一位置 1

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int unsetBit(int x, int pos) {
          return x & (~(1 << pos));
      }
  
      int setBit(int x, int pos) {
          return x | (1 << pos);
      }
  
      int flipBit(int x, int pos) {
          return x ^ (1 << pos);
      }
  
      vector<int> grayCode(int n) {
          if (n == 1) {
              return {0, 1};
          }
  
          vector<int> nums = grayCode(n - 1);
          int m = nums.size();
          int t;
  
          for (int i = 0; i < m; i++) {
              t = nums[m - i - 1];
              t = setBit(t, n - 1);
              nums.push_back(t);
          }
  
          return nums;
      }
  };

  1238. 循环码排列

  题意

  生成格雷码再反转

  分析

  生成格雷码，低位镜像对称，高位全置 1 即可。然后找到 start 位置，进行局部反转后整体反转即可。

  生成格雷码的过程可参考 89 题。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
  
      int unsetBit(int x, int pos) {
          return x & (~(1 << pos));
      }
  
      int setBit(int x, int pos) {
          return x | (1 << pos);
      }
  
      int flipBit(int x, int pos) {
          return x ^ (1 << pos);
      }
  
      vector<int> getGayCode(int n) {
          if (n == 1) {
              return {0, 1};
          }
  
          vector<int> nums = getGayCode(n - 1);
          int m = nums.size();
          int t;
  
          for (int i = 0; i < m; i++) {
              t = nums[m - i - 1];
              t = setBit(t, n - 1);
              nums.push_back(t);
          }
  
          return nums;
      }
  
      vector<int> circularPermutation(int n, int start) {
          vector<int> nums = getGayCode(n);
          int index;
  
          for (int i = 0; i < nums.size(); i++) {
              if (nums[i] == start) {
                  index = i;
              }
          }
  
          reverse(nums.begin(), nums.begin() + index);
          reverse(nums.begin() + index, nums.end());
          reverse(nums.begin(), nums.end());
  
          return nums;
      }
  
  };

  393. UTF-8 编码验证

  题意

  给定的是一连串 byte 数组，验证是不是 UTF-8 编码的字符集（可能有多个字符）

  分析

  其实这题是一个典型的 DFA 题型，每个字节输入有不同的状态，即首字节和非首字节，非首字节又有第几字节几种情况。

  不过这题状态较少，直接模拟也能写出来，就是 DFA 的跳转表写法。

  由于输入字节主要有两个状态，故我们需要一个计数器表示当前输入字节是哪个状态：

  1. cnt 为 0 表示输入的是第一个字节
  2. cnt 不为 0 表示输入的是后面的字节

  如果输入的不是第一个字节，直接判断当前字节是不是 10 开头的即可。并且 cnt - -

  而如果是第一个字节，则又要分多种情况。

  1. 开头 1 的个数多于 4 个，假
  2. 开头 1 的个数是 0，2，3，4，则 cnt 直接设为 1 的个数即可
  3. 其它情况都是假

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      bool validUtf8(vector<int>& nums) {
          int cnt=0;
          
          for (int i=0;i<nums.size();i++){
              if(cnt==0){
                  if((nums[i]&0b11111000)==0b11111000){
                      return false;               
                  } else if((nums[i]&0b11110000)==0b11110000){
                      cnt=3;                
                  } else if((nums[i]&0b11100000)==0b11100000){
                      cnt=2;
                  } else if((nums[i]&0b11000000)==0b11000000){
                      cnt=1;
                  } else if((nums[i]&0b10000000)==0){
                      cnt=0;
                  } else {
                      return false;
                  }
              } else {
                  if((nums[i]&0b10000000)!=0b10000000){
                      return false;
                  }
                  cnt--;
              }
          }
          return cnt==0;
      }
  };

基础

• list

  交换变量

  题意

  交换两数

  临时变量

  最简单的就是引入临时变量，没什么好说的

  class Solution {
  public:
      vector<int> swapNumbers(vector<int>& nums) {
          int t=nums[0];
          nums[0]=nums[1];
          nums[1]=t;
          return nums;
      }
  };

  异或

  第二种就是使用位运算异或，交换变量也是基本用法之一了。

  基本运算：x^x=0,x^0=x.

  class Solution {
  public:
      vector<int> swapNumbers(vector<int>& nums) {
  				// nums[0]:nums[0]^nums[1], nums[1]:nums[1]
          nums[0]^=nums[1]; 
  				// nums[0]:nums[0]^nums[1], nums[1]:nums[1]^nums[0]^nums[1]=nums[0]
          nums[1]^=nums[0];
  				// nums[0]:nums[0]^nums[1]^nums[0]=nums[1], nums[1]:nums[0]
          nums[0]^=nums[1];
          return nums;
      }
  };

  加减法

  加减法是另一个技巧，就是可能会溢出

  class Solution {
  public:
      vector<int> swapNumbers(vector<int>& nums) {
  				// nums[0]:nums[0]-nums[1], nums[1]:nums[1]
          nums[0]=nums[0]-nums[1];
  				// nums[0]:nums[0]-nums[1], nums[1]:nums[1]+nums[0]-nums[1]=nums[0]
          nums[1]=nums[1]+nums[0];
  				// nums[0]:nums[0]-(nums[0]-nums[1])=nums[1], nums[1]:nums[0]
          nums[0]=nums[1]-nums[0];
          return nums;
      }
  };

  效率

  三个方法复杂度都是一样的

  时间复杂度：$O(1)$

  空间复杂度：$O(1)$

  693. 交替位二进制数

  题意

  检查数字二进制的低位是否 0、1 交替，高位全零不管

  分析

  直接每次取最右边的位数，然后和当前应该是什么数比较即可，注意 flag 在 0 和 1 直接交替，可以用 x^1 实现。

  优化

  实际上，二进制的题很多都可以找规律解决掉。这题也是一样的。由于 01 交替，比如

  000000101010101，那么我们将其移位

  000000010101010，低位必然是一个 0 一个 1，所以我们可以异或

  000000111111111，再加上个 1，就必然变成

  000001000000000 这种只有一个 1 的数，所以我们可以用 x&(x-1) 清楚掉 1，结果必然等于 0.

  效率

  时间复杂度：模拟 $O(n)$，优化后 $O(1)$

  空间复杂度：$O(1)$

  代码

  模拟

  class Solution {
  public:
      bool hasAlternatingBits(int n) {
          int flag=n&1;        
          
          while(n!=0){
              n>>=1;
              
              if ((n&1)==flag){
                  return false;
              }
              
              flag^=1;
          }
                  
          return true;
      }
  };

  找规律

  class Solution {
  public:
      bool hasAlternatingBits(int n) {        
          int m=((n>>1)^n);
          if (m==INT_MAX){
              m=0;
          }else{
              m++;
          }        
          return (m&(m-1))==0;
      }
  };

  201. 数字范围按位与

  题意

  求 [left, right] 所有数相与的结果

  分析

  最直接的自然是遍历一遍了，但是会超时。所以我们得找规律。由于相与只有 1 与 1 相与为 1，其它为 0，所以我们要找位数相同的部分。

  假设 left=5，right=7，则

  5→0101

  7→0111

  要相与的话，显然 01x1 都相等，但是还有中间的数呢，即 6

  5→0101

  6→0110

  7→0111

  相同的部分为 01xx，所以结果为 0100，没看出来？继续

  假设 left=2，right=12，则

  2 → 00000010

  12→00001100

  相同部分为 0000xxx1，猜测一下，中间那些相与起来会是什么？显然我们只需考虑最低位和高 4 位就行了，因为其它位已经为 0 了。

  高 4 位会是什么？最低位又会是什么？

  2→0000xxx0

  3→0000xxx1

  4→0000xxx0

  5→0000xxx1

  6→0000xxx0

  7→0000xxx1

  8→0000xxx0

  9→0000xxx1

  10→0000xxx0

  11→0000xxx1

  12→0000xxx0

  我们发现高 4 位和左右边界一样都是 0000，而最低位则一直在 0，1 间交替，所以结果相同的部分应该是 0000xxxx，最后结果即为 0.

  根据上面的分析，其实我们可以得出结论了：

  1. 中间数字的高位和 left，right 的高位相同前缀一样
  2. 相同前缀后面的数则一直交替

  所以：数相与起来，就是 left,right 的相同前缀构成的数。 因为高位不变，低位交替相与就是 0。比如 5 和 7 的公共前缀就是 01xx，2 和 12 的公共前缀就是 0000xxxx。

  那么问题就变成：怎么寻找两个数的公共前缀。

  最简单的自然是模拟了，从左至右扫描一遍即可。

  优化

  我们也可以依次消除 right 最右边的 1，知道刚刚小于 left，这时的 rigth 就是公共前缀。

  效率

  时间复杂度：$O(1)$

  空间复杂度：$O(1)$

  代码

  暴力

  class Solution {
  public:
      int rangeBitwiseAnd(int left, int right) {
          int res=0xffffffff;
          
          for (int i=left;i<=right;i++){
              res&=i;
          }
          
          return res;
      }
  };

  模拟

  class Solution {
  public:
      int rangeBitwiseAnd(int left, int right) {
          int res=0;
          int a,b;
          
          for (int i=31;i>-1;i--){
              a=getBit(left,i);
              b=getBit(right,i);
              
              if (a!=b){
                  return res;
              }
              
              if (a==1){
                  res=setBit(res,i);
              } else {
                  res=unsetBit(res,i);
              }
          }        
          return res;
      }
      
      int getBit(int x,int pos){
          return (x>>pos)&1;
      }
      
      int setBit(int x,int pos){
          return x|(1<<pos);
      }
      
      int unsetBit(int x,int pos){
          return x&(~(1<<pos));
      }
  };

  消除 1

  class Solution {
  public:
      int rangeBitwiseAnd(int left, int right) {
          while(left<right){
              right&=(right-1);
          }
          return right;
      }
  };

  1684. 统计一致字符串的数目

  题意

  检查哪些字符串是由给定字符组成的

  分析

  要检查字符是否符合要求，就是个存在性问题，所以使用哈希表。而这题只检测字符，范围只有 24 个，所以我们可以用一个 int 变量来模拟哈希表，这样更简单一点。

  实际上，一些问题上经常可以可以这样简化哈希表的作用，比如统计字符个数，数字个数等，就可以用一个 24 或 9 长度的数组来代替，或者像这题一样，只是检测有限字符的存在性问题，也可以用 bitmap 来代替，而这题则比 bitmap 还要简化一点，即一个 int 变量就行了。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int countConsistentStrings(string allowed, vector<string>& words) {
          int cnt=0;
          int res=0;
          
          for (int i=0;i<allowed.size();i++){
              cnt=setBit(cnt,allowed[i]-'a');
          }
                  
          for (int i=0;i<words.size();i++){
              res++;
              for (int j=0;j<words[i].size();j++){                
                  if (!isExist(cnt,words[i][j])) {
                      res--;
                      break;                    
                  }
              }            
          }
          
          return res;
      }
      
      bool isExist(int x,char c){
          return getBit(x,c-'a')==1;
      }
      
      int getBit(int x,int pos){
          return (x>>pos)&1;
      }
      
      int setBit(int x,int pos){
          return x|(1<<pos);
      }
      
      int unsetBit(int x,int pos){
          return x&(~(1<<pos));
      }
  };

  898. 子数组按位或操作

  题意

  求所有连续子序列或之后结果的个数

  分析

  最简单的自然是直接双重循环生成所有连续子数组，然后在生成的过程中求得相或的结果。但是要得到的是不同结果的个数，即需要有一个去重的过程，故直接用 set 来暂存即可。

  优化

  本题数量级在 10^5，故暴力 $O(n^2)$ 显然会超时，故我们需要考虑优化。而最简单的优化就是进行一些剪枝操作，而不用更改基本思路。

  我们是怎么生成子数组的？在前一个子数组的基础上增加元素。而我们要求的是什么？或运算。

  这里我们就需要利用到或运算的性质了：一个数与另一个数或的结果，结果必然单调不减。

  其实也很好理解，毕竟或运算，原来的 1 还是 1，而 0 要么变 1，要么不变，总的来说数自然是在递增的了。

  所以说，我们固定左边界，右边界增加元素的过程中，所得到到子集或结果，也是递增的。

  而可以剪枝的地方就在这里：由于结果递增，那么如果这个结果已经达到了最大值，后面的所有子集或结果仍然是最大值，而我们只需要知道结果的个数，所以，后面子集不运算也不会影响结果。

  故，我们可以进行如下剪枝：

  1. 找到或结果的最大值
  2. 生成子集的过程中，判断结果是否大于最大值

  那么现在问题就转变为：怎么求或的最大值。

  我们前面说了，增加元素的或结果是递增的，那么元素最多时，自然结果必然就是最大值。

  所以，我们直接求得所有元素的或结果，就是最大值。

  效率

  时间复杂度：$O(n^2)$

  空间复杂度：$O(n)$

  代码

  暴力

  class Solution {
  public:
      int subarrayBitwiseORs(vector<int>& nums) {
          unordered_set<int> s;
          int t=0;
          
          for (int i=0;i<nums.size();i++){        
              t=nums[i];
              s.insert(t);
              for (int j=i+1;j<nums.size();j++){                
                  t|=nums[j];
                  s.insert(t);
              }             
          }
          
          return s.size();
      }
  };

  剪枝

  class Solution {
  public:
      int subarrayBitwiseORs(vector<int>& nums) {
          unordered_set<int> s;
          int t=0;
          int maxValue=0;
          
          for (int i=0;i<nums.size();i++){
              maxValue|=nums[i];
          }
          
          for (int i=0;i<nums.size();i++){        
              t=nums[i];
              s.insert(t);
              for (int j=i+1;j<nums.size();j++){                
                  t|=nums[j];
                  s.insert(t);
                  
                  if (t==maxValue){
                      break;
                  }
              }
          }
          
          return s.size();
      }
  };

  面试题 05.03. 翻转数位

  题意

  找出包含一个 0 的最长 1 的个数

  分析

  本题就是一个简单的变长滑动窗口，只是套了一个位运算而已。

  窗口中的状态就是含有 0 的个数，当小于等于一个时扩展，等于 1 个时收缩，每次扩展扩展收缩后更新长度即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int reverseBits(int num) {
          int res=0;
          int cnt=0;
          int l=0;
          int r=0;
          
          while(r<32){
              if (getBit(num,r)==0){
                  cnt++;
              }
              while(cnt==2){
                  if (getBit(num,l)==0){
                      cnt--;
                  }
                  l++;
              }
              r++;
              res=res>(r-l)?res:(r-l);
          }
          
          return res;
      }
      
      int getBit(int x,int pos){
          return (x>>pos)&1;
      }
  };

  面试题 05.01. 插入

  题意

  将 M 中的位数设置到 N 中

  分析

  遍历 M，然后写入 N 中对应位即可

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int insertBits(int N, int M, int i, int j) {
          for (int k=i;k<=j;k++){
              if (getBit(M,k-i)==1){
                  N=setBit(N,k);
              } else {
                  N=unsetBit(N,k);
              }
          }
          return N;
      }
      
      int getBits(int x,int pos,int cnt){
          return (x>>pos)&((1<<cnt)-1);
      }
      
      int getBit(int x,int pos){
          return (x>>pos)&1;
      }
      
      int unsetBit(int x,int pos){
          return x&(~(1<<pos));
      }
      
      int setBit(int x,int pos){
          return x|(1<<pos);
      }
  };

  717. 1 比特与 2 比特字符

  题意

  有两种特殊字符。第一种字符可以用一比特 0 来表示。第二种字符可以用两比特 (10 或 11) 来表示。

  现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由 0 结束。

  分析

  最简单的就是模拟，要问最后是不是只是一个 0，那么从左边开始放位置，遇到 1 就跳过一个位置，遇到 0 就继续，看最后是不是就是一个 0 即可。

  优化

  其实这题在分布上有一点规律，我们知道，一共三种分布：

  0

  10

  11

  我们从最后开始往前扫描，显然最后一个比较为 0 才行，即

  xxx0

  如果 0 前面没有 1，即

  0000

  显然是满足的

  如果 0 前面只有一个 1，即

  xxxx010

  再往前一位就是 xxx0010 或 xxx1010

  对于 xxx0010，连续两个 0 必然会被消掉，无论是 xx x0 0 10 还是 xxx 0 0 10 这两种情况，所以最后剩下的必然是 10 两位，即不满足。

  同理，对于 xxx1010，只有 xxx x1 0 10 或 xxx 10 10 这两种情况，最后 10 还是不满足。

  如果 0 前面有两个 1，即

  xxx0110

  那么就有 xx x0 11 0 和 xxx 0 11 0 这两种消除的情况，所以满足

  对于三个 1 的，根据上面的规律，不满足。

  所以我们可以找到规律了，即对于最后 xxxx0111...1110 中 1 的个数，如果是奇数，则不满足，如果是偶数，则满足。

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  模拟

  class Solution {
  public:
      bool isOneBitCharacter(vector<int>& nums) {
          int i;
          
          if (nums[nums.size()-1]==1){
              return false;
          }
          
          for (i=0;i<nums.size()-1;i++){
              if (nums[i]==1){
                  i++;
              }
          }
          
          return i==nums.size()-1;
      }
  };

  统计最后 1 的个数

  class Solution {
  public:
      bool isOneBitCharacter(vector<int>& nums) {
          int cnt=0;
          if (nums[nums.size()-1]==1){
              return false;
          }
          
          for (int i=nums.size()-2;i>-1;i--){
              if (nums[i]==1){
                  cnt++;
              } else {
                  return cnt%2==0;
              }
          }
          
          return cnt%2==0;
      }
  };

  397. 整数替换

  题意

  给定一个正整数 n ，你可以做如下操作：

  如果 n 是偶数，则用 n / 2 替换 n 。
  如果 n 是奇数，则可以用 n + 1 或 n - 1 替换 n 。
  n 变为 1 所需的最小替换次数是多少？

  分析

  基本操作如下：

  1. 当低位为 0 时，即为偶数时，直接右移
  2. 当低位为1 时，++ 或 —

  要把一个数变成 1，要把 n 变成 1，即 0000 0001，所以最后的结果，必然只有一个 1。

  无论这个 1 出现在什么地方，后面的操作都是移位。

  显然当低位为偶数时，移位不会影响 1 的个数，所以要使得满足 1 的个数，最后得奇数时，即低位为 1 时进行操作才行。

  问题就在于，当低位为 1 时，我们究竟是 ++，还是 — 呢？也就是说，每次当低位为 1 时，我们都需要从两个策略中选择一个，问题就在于，怎么选。

  直接看，似乎看不出来，来个例子

  假设数 n 为 0111 1110，我们该怎么做呢？

  1. 偶数移位为 0011 1111

  现在问题来了，低位是 1，该怎么选。

  假设++，变成： 0100 0000

  假设—，变成 ： 0011 1110

  我们看到，++ 的时候，似乎 1 的个数一下子就从 6 个变成了 1 个，而 — 则还有 5 个。而我们的目的就是要通过 ++ 或 — 减少 1 的个数。

  那么为什么，上面 ++ 的时候能一下子减少这么多 1 的呢？其实很简单，因为最后是 xx111，一些 1 相邻，+1 自然会把这些 1 全部都消除掉。

  我们现在只来看最后数的两位：

  00 → 偶数

  01

  10 → 偶数

  11

  显然，00 和 10 结尾的都是偶数，所以不管。问题在于，以 01 结尾的奇数和 11 结尾的奇数怎么操作。

  按照我们上面的分析，以 11 结果的操作，进行 ++ 时，能一下子消除更多的 1.那么对于以 01 结尾的呢？

  01+1 = 10

  01-1 = 00

  显然，01 结尾的进行 — 时消除的 1 个数更多。

  所以现在我们能够进行如下算法：

  1. 最后两位是 00 或 10 的，右移一位
  2. 最后两位是 01 的，- -
  3. 最后两位是 11 的，++

  但是上面还有一个例外，就是 3，3 是 0011，但是如果先 ++ 变成 0100，就要再移两次，一共三次操作。而直接 - - 变成 0010，再 - - 变成 0001，就只有两次操作。

  所以根据上面的分析，我们知道了算法的思想，就是某次 ++ 或 - - 时，贪心的选择能消除 1 的个数最多的那个操作。

  但是根据上面 3 那个意外，我们也发现似乎这个贪心不一定就全部满足，所以：

  贪心选择消除 1 最多的操作 就一定等于 最后操作次数最少吗？

  这个就需要证明了。

  证明：略（我也不会）

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int integerReplacement(int t) {
          int res=0;
          long n=t;
                  
          while(n!=1){
              if ((n&1)==0){
                  n>>=1;
              } else if (((n&0b11)==0b11) && (n!=3)){                
                  n++;
              } else {
                  n--;
              }
  
              res++;
          }
          
          return res;
      }
  };

异或

异或是一个等价关系，应用非常广泛。

• list

  421. 数组中两个数的最大异或值

  题意

  分析

  优化

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  暴力枚举

  class Solution {
  public:
      int findMaximumXOR(vector<int>& nums) {
          int res=0;
          
          for (int i=0;i<nums.size();i++){
              for (int j=i+1;j<nums.size();j++){
                  res=max(res,nums[i]^nums[j]);        
              }  
          }
          
          return res;
      }
  };

  1863. 找出所有子集的异或总和再求和

  题意

  分析

  优化

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  1720. 解码异或后的数组

  题意

  由差分异或得出前缀异或

  分析

  这题就是前缀数组和差分数组的一个变形，只是运算变成异或了而已，而已相互转换都是异或运算，而不是加减了。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      vector<int> decode(vector<int>& nums, int a) {
          nums.insert(nums.begin(),a);
          
          for (int i=1;i<nums.size();i++) {
              nums[i]^=nums[i-1];
          }
          return nums;
      }
  };

  1486. 数组异或操作

  题意

  求数组异或的结果

  分析

  找个锤子规律

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int xorOperation(int n, int start) {
          int res=0;
          for (int i=0;i<n;i++) {
              res^=(start+i*2);
          }
          return res;
      }
  };

  1734. 解码异或后的排列

  题意

  给定差分异或数组，求原数组，且原数组是 1~n 的数组排列（答案唯一）

  分析

  已知

  $encoded[i]=perm[i]\oplus perm[i+1]$

  则

  $perm[i]=encoded[i]\oplus perm[i-1]$

  而已知 encoded 数组，故我们只需要知道 perm[0]，就能递推求出整个 perm 数组。现在问题就是：怎么求出 perm[0]?

  我们来看一下题目中还有哪些条件没有使用到：

  1. n 是奇数
  2. perm 数组是 1~n 的排列

  直接看上面似乎看不出来，实际上，我们可以进行如下推理

  $x=1\oplus 2\oplus 3\oplus ..\oplus n=p[0]\oplus p[1]\oplus p[2]\oplus ..\oplus p[n]=p[0]\oplus e[1]\oplus e[3]\oplus ..\oplus e[n-2]$

  则

  $p[0]=x\oplus e[1]\oplus e[3]\oplus ..\oplus e[n-2]$

  而 x 和 e 数组都是已知的，故我们先通过上面的公式得出 p[0]，再通过递归公式求出整个 perm 数组即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      vector<int> decode(vector<int>& e) {
          vector<int> p(e.size()+1);
          
          for (int i=1;i<=p.size();i++){
              p[0]^=i;
              if ((i%2!=0) && (i<e.size())){                
                  p[0]^=e[i];
              }
          }
  
          for (int i=1;i<p.size();i++){
              p[i]=p[i-1]^e[i-1];
          }
          
          return p;
      }
  };

  1072. 按列翻转得到最大值等行数

  题意

  可以对任意列进行反转，求最后行相等的个数

  分析

  如果行元素相等这个可能有很多种，可能有的行都是 1，有的行都是 0，而同时考虑很多行比较麻烦，但是只考虑一行的话，就很简单。

  首先，由于可以对任意列进行反转，那么任意给定一行，我们总能将其变成行相等的情况。这是没有问题的。

  那么假设数组分成很多不同类型的行，比如 1101 的有 a 种，0011 的有 b 种，那么我们要进行反转的话，只需要找到类型最多的那种行进行反转就行了。

  但是现在问题就出现了：

  反转类型 a 的行，类型 b 的行会不会同时也变成行相等的情况呢？

  比如说

  001

  001

  110

  110

  现在 001 类型和 110 类型都有两个，我们对 001 进行反转的时候，假如反转成 000，但是这个时候，110 类型的行也同时变成 111 这种行相等的情况了，所以最后的结果不是 2 而是 4 了。

  那么我们该怎么解决这个问题呢？或者说，有没有什么办法，把行的类型变成反转的时候不会影响其它行的情况呢？

  我们来看一下那些看上去明明类型不同，但是反转后却同时满足行相等的行，是什么情况：

  001

  110

  11101

  00010

  11101010

  00010101

  发现了吗？没错，这些行其实就是完全取反后的，如果两个行之间取反相等，那么对它们进行列上的反转时，它们会同时达到行相等的情况。

  那么现在问题就很简单了：

  我们可以把数组分成很多不同类型行的组合：比如 a 和 a 取反表示一类，如 110，001 表示一类，111 和 000 表示一类。

  然后找到类别最多的那种行进行反转，就是最后行相等最大的行数。

  有人可能觉得行取反还是一个类型感觉有点麻烦，那我们就预处理一下嘛，先把那些表示相反的行取反，转换成同一类。比如以第一位为例，0 开头取反就是 1 开头的，那我们把所有 1 开头的行取反，就全部变成 0 开头的了，就不存在取反还是同一类的情况了。

  由于要统计不同类别的个数，所以直接用个哈希表暂存一下即可，最后遍历取最值。

  总结一下，就是开一些桶，某个时刻只有一个桶能满足行相等。映射桶的方式也很简单，某行和这个行所有元素取反的行映射到同一桶。最后找出最多的个桶即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(n)$

  代码

  class Solution {
  public:
      int maxEqualRowsAfterFlips(vector<vector<int>>& mat) {
          unordered_map<string,int> m;
          string s;
          int res=0;
          
          for (int i=0;i<mat.size();i++){
              s.clear();
              for (int j=0;j<mat[0].size();j++){
                  if (mat[i][0]==1){
                      s+=('0'+ (mat[i][j]^1));
                  } else {
                      s+=('0'+ mat[i][j]);
                  }                            
              }
              m[s]++;
          }
          
          for (auto item:m) {
              res=max(res,item.second);
          }
          
          return res;
      }    
  };