以下是我原来学习位运算时的笔记。今天复习翻出来，顺手贴上。若有不妥请在评论中指出，我会尽快完善，谢谢。

我在学习位运算时参考了Matrix67牛的blog中的相关内容，并且向Ghost牛请教。这些都在下文中有所体现。

下面例子中a0表示运算前的值，a表示运算结果，mask表示掩码。它们都是整型。

1. 按位与：&
   1&1=1，0&1=0，1&0=0，0&0=0
   可见和1进行“按位与”运算则原位不变，和0进行“按位与”运算则原位变为0。利用这个性质，我们可以用“按位与”运算进行：
2. • 提取特定位、清零其余位：
     例如：mask中要保留的位上为1，其他位为0，a=a0&mask
   • 判断int的奇偶（效率比%2高得多）：
     例如：(a&1)==0则为偶数，反之为奇数。（原理：因为奇数二进制末位总为1，偶数总为0。原数与00…001进行按位与运算，就得到了a二进制末位的值。）
3. 按位或：|
   1|1=1，0|1=1，1|0=1，0|0=0
   可见和1进行“按位或”运算则原位变为1，和0进行“按位或”运算则原位不变。利用这个性质，我们可以用“按位或”运算进行：
4. • 将某些特定位置为1，其余位不变。
     例如：mask中要置1的位为1，其余位为0，a=a0|mask
5. 按位异或：^
   1^1=0，0^1=1，1^0=1，0^0=0
   可见和1进行“按位异或”运算则原位取反，和0进行“按位异或”运算则则原位不变。利用这个性质，我们可以用“按位异或”运算进行：
6. • 特定位取反
     例如：mask中要取反的位为1，其余为0，a=a0^mask
   • 不用中间变量交换两数的值
     例如：要交换a、b的值只需：a=a^b;b=a^b;a=a^b;即可。
     (原理：上式即a=(a^b)^(a^b)^b,b=a^b^b。由于一个数与它本身进行“按位异或”运算得到0，任何一个数与0进行“按位异或”运算得到它本身，故上式即是：a=[b的原值],b=[a的原值]。这样就达到了交换a、b的目的。)
7. 取反：~
   对二进制各位按位取反
8. 左移：<<
   将一个数的各个二进制位左移若干位。（左丢弃，右补零）。我们可以通过左移进行：
9. • int快速*2
     当左移时丢弃的高位不包含1时，则数每左移一位，相当该数乘以2
10. 右移：>>
    将一个数的各个二进制位右移若干位，右丢弃。对于无符号整数及正整数，左补0；对于负数，补0为“逻辑右移”，补1为“算术右移”，具体是哪个则取决于计算机系统。我们可以通过右移进行：
11. • int（正数）快速/2
      每左移一位，相当该数乘以2。

下面是一些例题（来自Matrix67牛的blog，刷蓝后见解）：

去掉最后一位(101101->10110)  x>>1
在最后加一个0(101101->1011010)  x<<1
在最后加一个1(101101->1011011)  (x<<1)+1
把最后一位变成1(101100->101101)  x | 1
把最后一位变成0(101101->101100)  (x | 1) – 1
最后一位取反(101101->101100)  x ^ 1
右数第k位取反(101101->101001,k=3)  x ^ (1 << (k-1))
取末三位(1101101->101)  x & 7
取末k位(1101101->1101,k=5)  x & ((1 << k)-1)
把末k位变成1(101001->101111,k=4)  x | ((1 << k)-1)
末k位取反(101001->100110,k=4)  x ^ ((1 << k)-1)

把右边连续的1变成0(100101111->100100000)  x & (x+1)
把右起第一个0变成1(100101111->100111111)  x | (x+1)
把右边连续的0变成1(11011000->11011111)  x or (x-1)
取右边连续的1(100101111->1111)  (x^(x+1)) >> 1
去掉右起第一个1的左边(100101000->1000,树状数组)  x & (x ^ (x-1))

下面是位运算的一个“直接”应用，即可非常便捷地将int值以二进制形式表示。下面是Ghost神奇地“一行转二进制”代码（a为int型，且已被赋值）。（不敢想象，这竟然就是我们第一次省选中的一道题。太可惜了我没参加-_-）

for(int i=0;i<32;i++,a<<=1) cout << (a<0);

由于位运算占用空间小、速度快，常常用来做搜索和DP的状态表示与压缩。下面是利用位运算的求n皇后问题的解的个数。方法来自Matrix67牛的blog。Ghost解释说，此法与一般方法本质相同，只是换了位运算的表示。但由于位运算的速度非常之快，这样一个改进就可以获得非常显著的效果。Matrix67牛的原话是“主程序调用test(0,0,0)后sum的值就是n皇后总的解数。试着理解这段无敌的程序吧。拿这个去交USACO，0.3s，暴爽。”

void test(unsigned long row, unsigned long ld, unsigned long rd){
  unsigned long pos,p;
  if (row != upperlim){
    pos = upperlim & ~(row | ld | rd);
    while (pos){
      p = pos & (-pos);
      pos -= p;
      test(row + p, (ld + p) << 1, (rd + p) >> 1);
    }
  }
  else sum++;
}