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

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

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

  1. 按位与: &

    1&1=1,0&1=0,1&0=0,0&0=0

    可见和1进行“按位与”运算则原位不变,和0进行“按位与”运算则原位变为0。利用这个性质,我们可以用“按位与”运算进行:

    • 提取特定位、清零其余位:

      例如:mask中要保留的位上为1,其他位为0,a=a0&mask

    • 判断int的奇偶(效率比%2高得多):

      例如:(a&1)==0则为偶数,反之为奇数。(原理:因为奇数二进制末位总为1,偶数总为0。原数与00…001进行按位与运算,就得到了a二进制末位的值。)

  2. 按位或: |

    1|1=1,0|1=1,1|0=1,0|0=0

    可见和1进行“按位或”运算则原位变为1,和0进行“按位或”运算则原位不变。利用这个性质,我们可以用“按位或”运算进行:

    • 将某些特定位置为1,其余位不变。

      例如:mask中要置1的位为1,其余位为0,a=a0|mask

  3. 按位异或: ^

    1^1=0,0^1=1,1^0=1,0^0=0

    可见和1进行“按位异或”运算则原位取反,和0进行“按位异或”运算则则原位不变。利用这个性质,我们可以用“按位异或”运算进行:

    • 特定位取反 例如: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的目的。)

  4. 取反:~ 对二进制各位按位取反

  5. 左移:<<

    将一个数的各个二进制位左移若干位。(左丢弃,右补零)。我们可以通过左移进行:

    • int快速*2

      当左移时丢弃的高位不包含1时,则数每左移一位,相当该数乘以2

  6. 右移:>>

    将一个数的各个二进制位右移若干位,右丢弃。对于无符号整数及正整数,左补0;对于负数,补0为“逻辑右移”,补1为“算术右移”,具体是哪个则取决于计算机系统。我们可以通过右移进行:

    • 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++;
}