位运算符

• & : 对应位都为1时，结果为1

• | : 对应位存在一个1时，结果为1

• ^ : 对应位不同时，结果为1

异或运算的逆元素是本身, 即两次异或同一个数，结果不变： a ^ b ^ b = a

• ~ : 对一个数进行单目运算，把这个数的补码中的 0 和 1 全部取反， 有符号整数的符号位在这 ~ 运算中同样会取反。

补码： 在二进制表示下，正数和 0 的补码为其本身，负数的补码是将其对应正数按位取反后加一。

在二进制表示下，正数和 0 的补码为其本身，负数的补码是将其对应正数按位取反后加一。

$$ 5 =(00000101)_2 \ -5 =(11111010)_2 \ -5_补 =(11111011)_2 \ -(-5) =(00000100)_2 = 4 $$

• << 和 >> : 将二进制向左（右）移动对应的位数的值，

$$ 11 =(00001011)_2 \ 11 << 3 =(01011000)_2 = 88 \ 11 >> 2 =(00000010)_2 = 2 $$

在 C++ 中，右移操作中右侧多余的位将会被舍弃，而左侧较为复杂：

• 对于无符号数，会在左侧补 0；
• 对于有符号数，则会用最高位的数（其实就是符号位，非负数为 0，负数为 1）补齐。左移操作总是在右侧补 0。

复合赋值位运算符

和 += , -= 等运算符类似，位运算也有复合赋值运算符： &= , |= , ^= , <<= , >>= 。（取反是单目运算，所以没有。）

位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符，所以使用时需多加注意，在必要时添加括号。

应用

• 嵌入式中对寄存器进行按位计算，取值，置位

• 高效地进行某些运算，代替其它低效的方式。

• 表示集合。（常用于 状压 DP 。）

• 要求进行位运算。

常用运算

操作	运算
取出整数 n 在二进制表示下的第 k 位	(n >> k) & 1
取出整数n 在二进制表示下的第 0 ~ k - 1 位 (后 k 位)	n & ((1 << k) - 1)
对整数 n 在二进制表示下的第 k 位取反	n xor (1 << k)
对整数 n 在二进制表示下的第 k 位赋值 1	n
对整数 n 在二进制表示下的第 k 位赋值 0	n & (~(1 << k))

表示集合

操作	集合表示	位运算语句
交集	a∩b	a & b
并集	a∪b	`a
补集	\overline	~a （全集为二进制都是 1）
差集	a∖b	a & (~b)
对称差	a△b	a ^ b

实际代码

• 幂运算

// 乘 2 的非负整数次幂
int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
  return n << m;
}

// 除以 2 的非负整数次幂
int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
  return n >> m;
}

// 对 2 的非负整数次幂取模
int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }


// 判断一个数是不是 2 的正整数次幂
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

// 取绝对值,在某些机器上，效率比 n > 0 ? n : -n 高。
int Abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
  /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
     若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
     需要计算 n 和 -1 的补码，然后进行异或运算，
     结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */
}

// 取两个数的最大/最小值
// 在某些机器上，效率比 a > b ? a : b 高。
// 如果 a>=b,(a-b)>>31 为 0，否则为 -1
int max(int a, int b) { return b & ((a - b) >> 31) | a & (~(a - b) >> 31); }
int min(int a, int b) { return a & ((a - b) >> 31) | b & (~(a - b) >> 31); }

//判断符号是否相同
bool isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >= 0;
}

// 交换两个数
void swap(int &a, int &b) { a ^= b ^= a ^= b; }

// 获取一个数二进制的某一位
// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) { return (a >> b) & 1; }

平常写除法是向 0 取整，而这里的右移是向下取整（注意这里的区别）: 即当数大于等于 0 时两种方法等价，当数小于 0 时会有区别，如： -1 / 2 的值为 0 ，而 -1 >> 1 的值为 −1 。

C++ STL bitset 容器

bitset 容器其实就是个01串。 可以被看作是一个bool数组。它比bool数组更优秀的优点是：

• 节约空间
• 节约时间
• 支持基本的位运算。在bitset容器中，8位占一个字节，相比于bool数组4位一个字节的空间利用率要高很多。同时，n位的bitset在执行一次位运算的复杂度可以被看作是n/32，这都是bool数组所没有的优秀性质。

包含在自带的，bitset 头文件中：

bitset 容器的声明

因为bitset容器就是装01串的，所以不用在< >中装数据类型，这和一般的STL容器不太一样。< >中装01串的位数。

如：（声明一个105位的bitset）

bitset<100000> s;

对bitset容器的一些操作

1、常用的操作函数

和其他的STL容器一样，对bitset的很多操作也是由自带函数来实现的

count(), any(), none()

count，数数的意思。它的作用是数出1的个数。即s.count()返回s中有多少个1.

s.count(); // s中有多少个1.
s.any();   // s中存在0, true, 反之则为false
s.none();  // s中不存在0， true

set(), reset(), flip()

set()函数的作用是把bitset全部置为1.

特别地，set()函数里面可以传参数。set(u,v)的意思是把bitset中的第u位变成v,v∈0/1。

s.set(); // 全部置为1
s.set(u,v); // 第u位变成v,v∈0/1

s.reset(); // 所有位置为0
s.reset(k); // 第k位变成0

s.flip(); //全部按位取反
s.flip(k);// 第k位取反

2、位运算操作在bitset中的实现

bitset的作用就是帮助我们方便地实现位运算的相关操作。它当然支持位运算的一些操作内容。编写程序的时候对数进行的二进制运算均可以用在bitset函数上。

另外，bitset容器还支持直接取值和直接赋值的操作：具体操作方式如下：

s[3]=1;
s[5]=0;

这里要注意：在bitset容器中，最低位为0。这与数组实现仍然有区别。

bitset的运算就像一个普通的整数一样，可以进行与(&)、或(|)、异或(^)、左移(<<)、右移(>>)等操作。

// bitset operators
#include <iostream>       // std::cout
#include <string>         // std::string
#include <bitset>         // std::bitset

int main ()
{
  std::bitset<4> foo (std::string("1001"));
  std::bitset<4> bar (std::string("0011"));

  std::cout << (foo^=bar) << '\n';       // 1010 (XOR,assign)
  std::cout << (foo&=bar) << '\n';       // 0010 (AND,assign)
  std::cout << (foo|=bar) << '\n';       // 0011 (OR,assign)

  std::cout << (foo<<=2) << '\n';        // 1100 (SHL,assign)
  std::cout << (foo>>=1) << '\n';        // 0110 (SHR,assign)

  std::cout << (~bar) << '\n';           // 1100 (NOT)
  std::cout << (bar<<1) << '\n';         // 0110 (SHL)
  std::cout << (bar>>1) << '\n';         // 0001 (SHR)

  std::cout << (foo==bar) << '\n';       // false (0110==0011)
  std::cout << (foo!=bar) << '\n';       // true  (0110!=0011)

  std::cout << (foo&bar) << '\n';        // 0010
  std::cout << (foo|bar) << '\n';        // 0111
  std::cout << (foo^bar) << '\n';        // 0101

  return 0;
}