位运算又称为位操作，指的是直接对二进制位进行的一系列操作。
AND( & )
按位与
1 & 1 = 1
1 & 0 = 0
0 & 0 = 0
1101 & 1100 = 1100
OR( | )
按位或
1 | 1 = 1
1 | 0 = 1
0 | 0 = 0
1001 | 1010 = 1011
XOR( ^ )
按位异或
1 ^ 1 = 0
0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
1101 ^ 1100 = 0001
NOT( ~ )
取反
~1 = 0
~0 = 1
~0111 = 1000
另：& | ^ ~ 是c或类c的编程语言中所用的位操作符。 除了~是单目运算符
其余的三个都是双目运算符。
移位运算
左移运算符: <<
在二进制表示下把数字同时向左移， 低位以0填充， 高位越界后舍弃。
右移运算符: >>
右移运算又分为算术右移和逻辑右移。
算术右移：
在二进制补码表示下，把数字同时向右移位，高位以符号位填充，低位越界后舍弃。
对于 n >> 1 在C/C++中相当于 n/2 下取整。
逻辑右移：
在二进制补码表示下把数字同时向右移动，高位以0填充，低位越界后舍弃。
C++并没有规定右移的方式，所以编译器不同，可能实现的方式也不一样。
不过说了这么多，总结下来其实就是:
00001 << 2 = 00100
00100 >> 2 = 00001
(n>>k) &1 取出整数n在二进制表示下的第k位
为什么求n的二进制第k位数 是n>>k&1?
1的二进制数中只有第0位数是1,当任意一个数x与1做与(&)运算时,无论二进制位数> =1上的数是多少,位数>=1的数，与1的二进制位数> =1的数做与(&)运算都是0,因为1的进制当位数> =1时其上的数都是0,所以要判断n的二进制的第k位数是0还是1时,只需要将n的二进制的第k位数移到第0位再与1做与(&)运算就可得出结果.
n & ((1 << k) - 1) 取出整数n在二进制表示下的第0~k-1位(后k位)
n ^ (1 << k) 把整数n在二进制表示下的第k位取反
n | (1 << k) 把整数n在二进制表示下的第k位赋值为1
n & (~(1 << k)) 把整数n在二进制表示下的第k位赋值为0
n ^ (1 << k) = n - (1<<k)
除以2
a / 2 = a >> 1
(a + b) / 2 == a + b >> 1 ( + - 运算的优先级高于 <<, >> )
判断奇偶
一个数的二进制数的最低位如果是1 则该数一定是奇数 否则一定是偶数
所以 用 a & 1 检测最低为是否位1
if(a & 1) cout<<"奇数";
else cout<<"偶数"
快速幂
状态压缩
以一个二进制数表示一个状态集合。
如 n = 1100 S = {2, 3} S表示状态所有为1的集合。
成对变换
当n 为偶数时 n ^ 1 = n + 1
当n为奇数时 n ^ 1 = n - 1
所以
(0,1) (2, 3) (4, 5)… 关于 ^1 运算 构成“成对变换”
这一性质常用于图论邻接表中边集的存储。在具有无向边（双向边）的图中把一对正反方向的边分别存储在邻接表数组中的第n和第n+1位置（n为偶数），就可以通过^1的运算获得与当前边（x, y） 反向的边（y, x）的存储位置。
摘自<<算法竞赛进阶指南>>
lowbit(n) 定义为非负整数n在二进制表示下"最低为1及其后边所有0"构成的数值. 例如 n = 10
的二进制表示为(1010)2, 则lowbit(n) = 2 =
$$
(10)_2 .
$$
lowbit(n) = n & (~n + 1) = n&(-n)
摘自<<算法竞赛进阶指南>>
我们知道，任何一个正整数都可以被表示成一个二进制数。如：
那么定义一个函数f=lowbit(x)f=lowbit(x)，这个函数的值是xx的二进制表达式中最低位的11所对应的值
比如:
所以假设一个数的二进制最低位的1在从右往左数的第k位，那么它的lowbit值就是
lowbit函数实现有两种方式：
一、
x&(x^(x-1))
二、
x&-x
简单解释一下：
我们得到lowbit的值，只需要得到最后一个1的位置，并且把除了这个位置之外的所有位置全部置成零。然后输出就可以。
那么我们看一看x&(x^(x-1))
拿上面的6举例：
我们发现，根据小学数学减法运算的借位原则，对一个二进制数进行减1，那么会出现从这个这个数的最后一个1开始到最后的所有数都取反，即构成一个01111?01111?的串。
我们把这个数与原数异或，就会造成：第一个1以后的数（包括第一个1）全部取1.其他的位全部取0.即构成一个由一堆0后面跟一堆1的串。
那么再把原式做一个与运算，那么除了原来的那个1（对应位都是1）为1，其他位全是0，完成任务。
那么我们再看一看x&-x
根据计算机补码的性质。
补码就是原码的反码加一
如：
反码：
加一：
可以发现变为反码后 x 与反码数字位每一位都不同， 所以当反码加1后神奇的事情发生了，反码会逢1一直进位直到遇到0，且这个0变成了1，所以这个数最后面构造了一个 100… 串。 由于是反码，进位之后由于1的作用使进位的部分全部取反及与原码相同，所以可以发现 lowbit 以前的部分 x 与其补码即 -x 相反， lowbit x 与 -x 都是1，lowbit 以后 x 与 -x 都是0 所以 x&-x 后除了 lowbit 位是1，其余位都是0。符合条件。
我们可以使用lowbit运算统计一个整数的二进制形式下1的个数。
实现原理很简单啦，就是：我们先用lowbit运算找出lowbit(x)lowbit(x)，然后用原数减去这个数，依次循环，直到为0为止。
这也是树状数组的实现原理。
代码：
while(x)
{
x-=x&-x;
ans++;
}
关于lowbit运算，最著名的应用应该算是树状数组。但是lowbit的神妙远远不止树状数组，在很多二进制和位运算的相关题目中，都有lowbit运算的影子。甚至，在状态压缩DP中，lowbit也扮演着一份不可忽视的角色。
注：参考 https://www.cnblogs.com/fusiwei/p/11752540.html
原文：https://www.cnblogs.com/MyBlogForRecord/p/14672053.html