本文分两部分，第一部分列举几个有趣的位操作，第二部分讲讲算法中常用的 n & (n - 1) 操作以及异或运算，顺便把用到这些技巧的算法题列出来讲解一下。因为位操作很简单，所以假设读者已经了解与、或、异或这三种基本操作。

位操作（Bit Manipulation）可以玩出很多奇技淫巧，但是这些技巧大部分都过于晦涩，没必要深究，咱们只要记住一些有用的操作即可。

一、几个有趣的位操作

1. 利用或操作|和空格将英文字符转换为小写

('a' | ' ') = 'a'
('A' | ' ') = 'a'

2. 利用与操作&和下划线将英文字符转换为大写

('b' & '_') = 'B'
('B' & '_') = 'B'

3. 利用异或操作^和空格进行英文字符大小写互换

('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'

以上操作能够产生奇特效果的原因在于 ASCII 编码。字符其实就是数字，恰巧这些字符对应的数字通过位运算就能得到正确的结果，有兴趣的读者可以查 ASCII 码表自己算算，本文就不展开讲了。

4. 判断两个数是否异号

int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true

int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false

这个技巧还是很实用的，利用的是补码编码的符号位。如果不用位运算来判断是否异号，需要使用 if else 分支，还挺麻烦的。读者可能想利用乘积或者商来判断两个数是否异号，但是这种处理方式可能造成溢出，从而出现错误。

5. 不用临时变量交换两个数

int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1

6. 加一

int n = 1;
n = -~n;
// 现在 n = 2

7. 减一

int n = 2;
n = ~-n;
// 现在 n = 1

PS：上面这三个操作就纯属装逼用的，没啥实际用处，大家了解了解乐呵一下就行。

二、算法常用操作

n&(n-1)—Brian Kernighan 算法

n&(n-1)这个操作是算法中常见的，作用是消除数字n的二进制表示中的最后一个 1。

看个图就很容易理解了：

其核心逻辑就是，n - 1 一定可以消除最后一个 1，同时把其后的 0 都变成 1，这样再和 n 做一次 & 运算，就可以仅仅把最后一个 1 变成 0 了。

n&-n

取n最低比特位

inline static int lowbit(int x) {
        return x & -x;
}

x&-x表示取x最低位为1的那个数。即m = x&-x,则x%m = 0且\(m=2^k\), 如果x为奇数， m =1。例如：

x  = 10000110
-x = 01111001 + 1 = 01111010
x&-x = 00000010

置位操作

• [ ] 判断:j位为1：（x>>j)&1
• [ ] set j 位为1：x |(1<<j)
• [ ] set j位为0: x&~(1<<j)

max/min函数

int x;  // we want to find the minimum of x and y
int y;   
int r;  // the result goes here

在分支跳转指定代价很高，没有condition move指定的机器上：

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

On some rare machines where branching is very expensive and no condition move instructions exist, the above expression might be faster than the obvious approach, r = (x < y) ? x : y, even though it involves two more instructions. (Typically, the obvious approach is best, though.) It works because if x < y, then -(x < y) will be all ones, so r = y ^ (x ^ y) & ~0 = y ^ x ^ y = x. Otherwise, if x >= y, then -(x < y) will be all zeros, so r = y ^ ((x ^ y) & 0) = y. On some machines, evaluating (x < y) as 0 or 1 requires a branch instruction, so there may be no advantage.

To find the maximum, use:

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

以上便是一些有趣/常用的位操作。其实位操作的技巧很多，有一个叫做 Bit Twiddling Hacks 的外国网站收集了几乎所有位操作的黑科技玩法，感兴趣的读者可以查看：

http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel