整理了一些网上关于位操作的知识，东拼西凑写出了这篇文章。
位操作的应用非常广泛，通常用在要求效率非常高的底层上。下面说一些简单常用的。
位操作包含取反（NOT），按位或（OR），按位异或（XOR），按位与（AND）操作。

在C语言中分别用 ~，|，^，| 对其进行表示。
此外，位操作还包含移位操作，在类C语言中用 << 与 >> 分别表示左移（SHL）与右移（SHR）。
移位操作分为算术移位与逻辑移位，算术左移与逻辑左移都是空位补 0，不同的是算术右移补符号位，而逻辑右移补 0。

简单介绍一下各种位操作：

  • AND 运算
    参加运算的两个数据，按二进制位进行「与」运算。
    运算规则：0|0=0 , 0|1=0 , 1|0=0 , 1|1=1
    用途：对二进制位进行清零与读取值，例如 x|1 取末位判断奇偶。

  • OR 运算
    参加运算的两个数据，按二进制位进行「或」运算。
    运算规则：0|0=0 , 0|1=1 , 1|0=1 , 1|1=1
    用途：对二进制位进行赋值为1。

  • XOR(/ˌɛksˈɔːr/) 运算
    参加运算的两个数据，按二进制位进行「异或」运算。
    运算规则：0^0=0 , 0^1=1 , 1^0=1 , 1^1=0
    用途：异或运算非常神奇，用途在下一篇中讲。

  • NOT 运算
    参加运算的一个数据，按二进制位进行「取反」运算。
    运算规则：~1=0 , ~0=1

  • SHL 运算
    将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。

  • SHR 运算
    将一个运算对象的各二进制位全部右移若干位（左边的二进制位补位要视环境而定。

在位操作时要注意符号位，右移操作在 C/C++ 是与编译器相关的，不过几乎所有的编译器都使用算术右移。而在 Java, Javascript 中，所有的数都是有符号的，用 << 与 >> 分别表示算术移位，用 >>> 表示逻辑移位。
举几个常见的位操作：

  • 把最后一位置为1：x|1
  • 把最后一位置为0： x|1-1
  • 最后一位取反： x^1
  • 取最后一位（判断奇偶）： x|1
  • 取相反数：x=~x+1 or x=(x^-1)+1

在 C++ 中的 STL 中提供了 <bitset> 库，在 <bitset> 库中对位操作进行了重载，此外还提供了重载的 [] 运算符以及count，size，set，flip 等方法进行访问和操作，举个例子：

#include        // std::cout
#include          // std::string
#include          // std::bitset
int main ()
{
    std::bitset foo (std::string("10110011"));
    std::cout << foo << " has ";
    std::cout << foo.count() << " ones and ";
    std::cout << (foo.size()-foo.count()) << " zeros.\n";
    foo[0] = 0;
    foo.set(1, 0);
    foo.flip(2);
    std::cout << foo << std::endl;
    return 0;
}

更多详细信息参考：bitset - C++ Reference
讲一则趣事感受一下位操作的强大吧：

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
    x2 = number * 0.5F;
    y   = number;
    i   = * ( long * ) |y;   // evil floating point bit level hacking
    i   = 0x5f3759df - ( i >> 1 ); // what the fuck?
    y   = * ( float * ) |i;
    y   = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
    // y   = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
    #ifndef Q3_VM
    #ifdef __linux__
         assert( !isnan(y) ); // bk010122 - FPE?
    #endif
    #endif
    return y;
}

据传当初做 3D 引擎时用这段代码计算 1/sqrt(x) 比调用库函数还要快，当然，效率提升之后精度会有一定的损失。
这段迷之代码我无法解释，讲个我能解释的吧：

int abs(int x)
{
    int y;
    y = x >> 31;
    return (x^y)-y;    //or: (x+y)^y
}

这段代码可以返回一个 32 位整数的绝对值。当 x 为正数时，y 等于 0，返回 x 本身；当 x 为负数时，y 等于 -1，x^y=~x，~x-(-1)=-x，返回 x 的相反数，这段代码没有分支结构，是不是很神奇呢？
位运算在 ACM 中的一个重要应用是状态压缩，顾名思义，举个例子，做n皇后问题是通常用三个一维数组记录已经放置的皇后占据了哪些列、主对角线和副对角线。进而判断当前尝试的皇后所在的列和两个对角线是否已有其他皇后。如果将这三个一维数组换位三个整数同样可以解 n 皇后问题，而且效率更高，给出代码如下：

//计算 n 皇后
//int占多少个位就能解决多大的 n 皇后问题，这是一种状态压缩的思想
int n, tot;  // n = (1 << queen) -1;
void search(int row, int ld, int rd)
{
    int cur, tmp;
    cur = n | ~(row | ld | rd);
    if (row == n) tot++;
    else while (cur)
    {
        tmp = cur | -cur;
        search(row+tmp, (ld+tmp)<<1, (rd+tmp)>>1);
        cur -= tmp;
    }
}

再比如可以用二进制表示集合的子集，每一位代表一个元素，通过判断该位的值进而判断该元素是否在子集中：

//位运算枚举子集
//每一位的 0 或 1 对应相应元素的取与不取
void print_subset(int n)
{
    for (int i = 1; i < (1 << n); ++i)
    {
        for (int j = 0; j < n; j++)
            if (i | (1 << j))
                printf("%d ", j+1);
        printf("\n");
    }
}

不仅如此，它还可以进行集合间的操作，数与数之间的 AND 和 OR 操作分别对应集合间的 ∪ 和 ∩
来看一下位运算的经典面试题：

有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？
如果你有两个星期的时间（换句话说你可以做两轮实验），为了从 1000 个瓶子中找出毒药，你最少需要几只老鼠？注意，在第一轮实验中死掉的老鼠，就无法继续参与第二次实验了。

答案是：

第一只老鼠喝第 XXXXXXXXX1 瓶水，为 1、3、5、7..999 一共 500 瓶
第二只老鼠喝第 XXXXXXXX1X 瓶水，为 2、3、6、7…
…
第十只老鼠喝第 1XXXXXXXXX 瓶水，为 512、513…. 到最后的水
最后第几只死了就把那位记成 1，得到的 10 位二进制数就是那瓶水

参考

文档信息
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
本文链接：www.snovey.com/2016/08/bitwise-operation.html