3.4　有用的位运算

尽管位运算有点抽象，但是其在有些场合非常有用。本节使用多种语言展示位运算的一些有用的属性。

3.4.1　使用AND运算判断位串中的一位

可以使用按位AND运算来判断位串中的某一位是0还是1。将数值和只有该位为1的位串进行AND逻辑运算，如果该数值对应的位为0，则AND运算的结果为0，如果为1，则AND运算的结果非零。下面这段C/C++代码通过检查整数的第0位来判断该整数是奇数还是偶数：

二进制形式的按位AND运算如下：

如果 ValueToTest 的低位为0，则结果为0。如果 ValueToTest 的低位为1，则结果为1。计算忽略了 ValueToTest 其他的位。

3.4.2　使用AND运算判断多个位为零或非零

按位AND运算还可以用来判断多个位是否全部为0。例如，判断数值是否可以被16整除，则可以检查低 4位是否全部为0。使用按位AND运算进行判断的Free Pascal/Delphi语句如下：

二进制形式的按位AND运算如下：

当且仅当 ValueToTest 的低4位均为0时，结果为0。

3.4.3　比较二进制字符串中的多个位

可以使用AND和OR运算比较二进制值中的某些位。比如比较一对32位值中的第0、1、10、16、24及31位。技巧是把两个值中不需要比较的位设置为0，然后再来比较。

考虑以下三个二进制值，x表示不需要关心该位的值：

前面两个二进制值（我们只对第31、24、16、10、1及0位感兴趣）相等。如果将前两个值中的任何一个与第三个值进行比较，就会发现它们不相等。而且第三个值大于前两个值。在C/C++和汇编语言中比较这几个值的代码如下：

3.4.4　使用AND运算创建模 n 计数器

模 n 计数器 （Modulo-n Counter）从0开始计数，达到最大值后重新从0开始计数 。模 n 计数器非常适合创建重复的数字序列，例如0，1，2，3，4，5，…， n -1；0，1，2，3，4，5，…， n -1；0，1，…。这种数字序列可用来创建循环队列以及其他超出范围就重用数组元素的数据结构对象。模 n 计数器常见的创建方法是将计数器加1，再将结果除以 n 并保留余数。下面是C/C++、Pascal及Visual Basic中模 n 计数器的代码实现：

然而，除法运算的成本高昂，比加法需要更多的执行时间。而使用比较运算代替余数运算来实现模 n 计数器更加高效。下面是一个Pascal的例子：

在某些特殊情况下，例如当 n 为2的幂时，使用AND运算递增模 n 计数器更加高效便捷。递增模 n 计数器，然后和x=2 ^m -1（2 ^m -1的第0～m-1位为1，其他位全部为0）进行AND逻辑运算就可以了。AND运算比除法运算要快得多，因此用AND运算实现模 n 计数器比使用余数运算高效得多。对大多数CPU来说，使用AND运算比使用if语句要快得多。下面的例子展示了如何使用AND运算实现 n =32的模 n 计数器：

汇编语言的代码也特别高效： PNKTwRXtD/jjao9pmHB+zx3Mk/Den0jBSvHJ3YgVgj72YIRsZiHNJAIoXdoOTSlI