位运算的技巧

基本

and 运算

通常用于二进制取位操作。

例如，and 1就是取二进制末位，可以用来判断一个数的奇偶性。

or 运算

通常用于二进制特定位上的无条件赋值。

例如，or 1 就是把最末位强行变为1。

xor 运算

通常用于对二进制的特定位进行取反操作。

0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0

上面可以看到与 0 异或不变，与 1 异或取反。同时也可以看做不带进位的加法。

异或的逆运算是它本身，也就是两次对同一数进行异或结果不变，可以用来进行简单的加密。

利用上面的原理，异或可以用来进行交换：

a = a ^ b
b = a ^ b
a = a ^ b

not 运算

使用 not 运算的时候要注意是否带符号，如果是无符号数，则会得到它与上界的差。

左移运算

通常认为左移一位要比乘2要快，因为前者操作更底层。

右移运算

和左移一样可以用来代替除2，效率会大大提高。

---

判断一个数是不是2的次幂

如果一个数是2的次幂，那么该数和比自己小1的数相 与 会等于 0，同时 0 并不是2的次幂，所以我们可以通过下面的代码来判断，而不是循环除2直到等于1：

<pre>
unsigned int v; // we want to see if v is a power of 2
bool f; // the result goes here

f = v && !(v & (v - 1));
</pre>