位运算的运用

位运算可以用来做什么？

位运算

众所周知，常用的位运算有&（与），|（或），^（异或），<<（左移），>>（右移），~（取反）几种。

位运算虽然简单，但是在应用上有很多技巧。

位的访问可以简单的使用一个移位操作和一个与操作来实现。下面的程序就演示了检测第$pos$位上是不是$1$：

1
2
3

bool getPos(unsigned int x, int pos){
    return (x >> pos) & 1;
}

而要访问第$pos$位开始向后的连续$t$位，就要使用一个“遮罩”来捕获后面的那些位。使用与运算就可以做到这一点。如下面代码所示：

1
2
3

int getPosT(unsigned int x, int pos, int t){
    return (x >> pos) & ((1u << t) - 1);
}

要将第$pos$位修改为$1$可以使用或运算。如下面的演示程序：

1
2
3

unsigned int setPos(unsigned int x, int pos){
    return x | (1u << pos);
}

要将第$pos$位修改为$0$可以将原数与一个只有$pos$位上是$0$，其余位均为$1$的数相与，如下程序所示。

1
2
3

unsigned int delPos(unsigned int x, int pos){
    return x & ~(1u << pos);
}

要将第$pos$位取反可以将原数与一个只有$pos$位上是$1$，其余位均为$1$的数相异或，如下程序所示。

1
2
3

unsigned int flipPos(unsigned int x, int pos){
    return x ^ (1u << pos);
}

这个是经典的lowbit方法。代码如下：

1
2
3

unsigned int lowbit(unsigned int x){
    return x & (-x);
}

原理是补码为反码$+1$。

参考资料：