我们现在知道，你通过电脑或者智能手机获得或处理的所有信息，在计算机内部都是用二进制数字表示的。本章将描述二进制相关的一些基本概念以及常见的二进制运算。
比特（bit）是二进制数据的最小表述单元，每个比特可取 0 或 1 两个值。通过前述的逻辑门的组合，可以形成加法器等运算单>元以及逻辑运算及控制单元，从而完成复杂的算术运算。在衡量电子计算机之运算能力的参数中，最常见的有 32 位、64 位的概念。这表示电子计算机能够同时处理的比特位数。比如，32 位电子计算机，在一个时钟周期内（电子计算机中时钟的作用，相当>于指挥三体人的人肉计算机阵列的旗帜；一个时钟周期相当于指挥者的旗帜挥动一次），可以完成 32 位比特的加法运算；而 64 位电子计算机，则可以完成 64 位比特的加法运算。
另外，除了加法运算之外，电子计算机可以完成其他的操作，如逻辑运算、访问存储单元等等。这些可在一个或多个时钟周期内完成的不可拆分操作被定义为电子计算机的指令，而复杂的运算和逻辑算法，就是指令及其数据的有序集合。进而，每秒可以执行的计算机指令数量就变成了衡量电子计算机运算速度的一个重要指标。在电子计算机出现的早期阶段，运算能力相对较弱，该指标的单位通常称为“每秒千指令（kIPS）”，而当今的电子计算机，该指标的单位通常称为“每秒百万指令（MIPS，Millions of Instructions per Second）”。以英特尔酷睿 2 P8800 CPU 为例，在时钟频率为 2.66GHz 时的运算速度为 7047.88 MIPS1。显然，电子计算机可同时处理的二进制比特位数量越大、每秒指令数越高，其性能越好。
类似地，人们使用每秒浮点运算次数（亦称每秒峰值速度）这一指标来衡量超级计算机的运算能力。每秒浮点运算次数（FLOPS，Floating-point operations per second）指计算机每秒可执行的浮点数操作次数。中国天河二号超级计算机目前保有此项指标的>世界纪录，为 33.86 PFLOPS2，公布于 2013 年。
需要注意的是，一条电子计算机指令的执行需要一个时钟周期或者多个时钟周期。比如对简单的二进制逻辑运算（与、或等）或者加法，通常在一个时钟周期内即可完成；但对复杂的乘除法或者浮点运算，则需要多个指令周期才能执行完毕。这很容易理解，比如整数的乘法操作，就是重复执行多次加法的结果。
尽管计算机最基本的信息存储单位是比特，但如果我们始终使用比特这个单位来表达数据，则会非常麻烦。因此，人们选择使用八个比特为一个单位来表示计算机所处理的数据。八个比特形成一个字节（Byte）。选择八比特作为最基本的计算机信息计量单位，大致原因有二。其一，8 是 2 的 3 次方，便于进行二进制处理；其二，八位比特可表达 0~255 总共 256 个数字，比起两位比特（4 个数字）或者四位比特（16 个数字）能表达的数字个数多，但又比十六位比特为单位情况下能表达的数字个数（65,536）少，基本上恰恰好。因此，字节作为衡量计算机信息量的基本单位一直沿用至今，比如衡量电子计算机的存储能力（内存大小、硬盘容量等）时，使用的就是字节这个单位。
有关比特和字节的计量，读者需要了解如下习惯用法：
- 在计算机领域，K、M、G、T、P、E、Z、Y 分别用来表示千（1K=1,024）、兆（1M=1,024K）、吉（1G=1,024M）、太（1T=1,024G）、拍（1P=1,024T）、艾（1E=1,024P）、泽（1Z=1,024E）、尧（1Y=1,024Z）等单位前缀。注意这些单位前缀以 1,024（210）作为倍数逐级增加单位量；但在其他科学界，这些单位前缀又往往使用 1,000 作为倍数。这的确带来了一定程度上的混乱2。准确的方法是在使用 1,024 作为倍数时，在这些单位前缀后面增加小写的 i 作为后缀。比如，1MiB，表示的就是 1,024 字节，>而 1MB 表示 1,000 字节。但如果是在计算机领域，如果不添加i 后缀，往往默认使用 1,024 倍数。
- 小写的 b 通常用来表示比特，而大写的 B 通常用来表示字节。在通信领域，人们经常使用 bps（bits per second）这个单位来衡量通信线路的容量或速率。比如，当前智能手机所使用的 3G 通信标准可达到 20Mbps 的下行传输速率，亦即每秒可传输 20M 比特。需要注意的是，这个数字除以 8 并不能得到以字节为单位的传输速率，因为在传输过程中，会使用一些冗余的比特位（比如校验位，用来校验所传输数据的准确性）。举例说明，在 8Mbps 的传输速率中，作为最终用户基本上无法获得 1MBps 的传输速率。
下图给出了一个典型字节的比特位组成：
图 2-1 一个典型的字节
注意其排列顺序，最左侧的位称为“最高位（most significant bit，MSB）”，最右侧的位称为“最低位（least significant bit，LSB）”。这一排列顺序和书写十进制数字时左侧表示高位、右侧表示低位是一样的。
为了便于记述，人们又使用十六进制方式来表述一个字节，分别用十六进制的符号（0, 1, …, 9, A, B, …, F）来表示高低四位比特。这样，上图中的字节可表示为 0x0F 或者0Fh。前者使用 0x 作为前缀表示这是一个十六进制表达的字节，后者使用 h 作为后缀来表示这是一个十六进制表达的字节。类似地，人们还使用 b 作为后缀来表示字节的二进制表达，如 00001111b。如果不使用>前缀或者后缀，则表示十进制的表达，如 15。当前，这种表达方法作为约定俗成，被大部分编程语言或者计算机相关技术文献使用。
另外，除了字节之外，人们还经常使用“字”（word）来表达一个 16 位的二进制数，或简称十六位元；用“双倍字”（dword，double word）来表达一个 32 位的二进制数，或简称三十二位元；用“四倍字”（qword，quadruple word）、“双四倍字”（dqword，double quadruple word）分别表示 64 位、128 位二进制数等等。
字节序（byte order）指电子计算机处理器在处理多字节的数据对象（比如字、双字、四倍字以及接下来讲述的浮点数）时，在寄 存器及内存中以什么样的顺序保存字节。
我们知道，桌面系统通常运行在英特尔的 x86 架构处理器上，而这种处理器按照低地址存放低位数据的原则保存多字节数据对象。假定整数 0x1234 是一个 16 位整数，则在 Intel x86 平台上，处理器将按图 2-2 所示的方式存储这个整数。即低地址 A 中保存 0x34 这个字节，而在高地址 A+1 中，保存 0x12 这个字节。这种字节序称为“小头（little-endian）”。见图 2-2。
图 2-2 小头（little-endian）存储
大头系统存储多字节数据对象时，采用和小头系统完全相反的方式，见图 2-3。
图 2-3 大头（big-endian）存储
许多 RISC 处理器都使用大头字节序，比如 PowerPC、M68k等（ARM 和 MIPS 处理器可灵活设置采用哪种字节序，通常被设置为小头）。ARM 处理器还有一个特殊之处，即整数的表述通常被设置为小头系统，但始终使用大头字节序来存储浮点数。
除了常见的小头存储和大头存储方式之外，还有一种 32 位整数的存储方式，即 PDP ENDIAN。PDP ENDIAN 很少使用，它在存储 32 位整数时，用来形成 32 位整数的两个 16 位整数采用大头存储形式，而形成 16 位整数的两个 8 位字节却采用小头存储形式。图 2-4 给出了这三种 ENDIAN 系统存储 0x04030201 这个 32 整数时的字节顺序。
图 2-4 Little-endian、Big-endian 以及 PDP-endian 对 32 位整数的存储顺序
通常在我们的程序开发过程中，不同的大小头并不会给我们带来大的麻烦。但是，假如我们将一个小头的二进制数保存在一个文件中，然后再在大头的系统上读取时，就可能出现问题。这是因为：
- 将一个多字节二进制数保存到文件中时，将保留字节在处理器内部存储的顺序；
- 文件的读取操作都是以字节为单位进行的。
比如在小头系统上，我们使用如下的伪代码3将 0x1234 这个 16 位整数保存到某个文件：
WORD my_word = 0x1234
FILE my_file = OPEN ("temp.bin")
WRITE (my_file, my_word)
CLOSE (my_file)
当我们再次从文件中读取这个整数时，我们可以用下面的伪代码：
WORD my_word
STDIO::FILE my_file = STDIO.fopen ("temp.bin")
my_word = STDIO.fread (my_file, 2)
STDIO.fclose (my_file)
如果上述代码仍然小头处理器上运行，则调用 READ 过程之后，my_word 中的值仍然为 0x1234。然而，当我们在大头处理器上执行上述读取代码时（这里假定文件由小头系统写入），我们会发现 my_word 的值变成了 0x3412。因此，我们要特别注意多字节二进制数据在不同处理器架构上的读写问题。
字节序的问题，通常在我们从文件或者网络中读取一个不同于本机字节序的多字节二进制数据时出现，也就是使用某种中介传送数据时出现。如果我们的程序从来不从文件系统或者网络中读取 8 位以上的整数或者浮点数，或者始终发生在使用同一种处理器的计算机上时，则程序不必关心字节序问题。因为这种情况下，所有的整数或者浮点数都会采用相同的字节序，即兼容于处理器的字节序来处理。然而，现实情况中，我们经常需要读取一些已经存在的文件来获得数据。比如，图形应用程序经常要读取一些图片文件，而这些图片文件可能是由运行在 PC 上的应用软件保存的，这时，就有可能出现字节序不匹配的问题。像我们常用的 Windows BMP 文件，会使用 32 位整数来保存图片的大小信息，且以小头字节序保存，如果我们要在大头系统上正确读取BMP 文件，就需要首先对读取的 32 位整数做字节序转换，才能正确使用。
当然，还有一种简单的方法可以绕开字节序的问题，即将所有的多字节数据在存储或传输时，始终使用可打印的字符来表示。这种方法在计算机软件中一般称为序列化，将在后面的章节中介绍。序列化处理后，所有复杂的多字节数据将转换为可打印的字符（单个字节）序列，即字符串或俗称“文本”，读取后做反序列化操作即可。
在 C 语言中，我们如何判断程序运行在大头系统还是小头系统上呢？我们可以通过清单 2-1 中的 is_big_endian 函数来判断。
清单 2-1 判断目标系统的字节序（check_endian.c）
#include <stdio.h>
inline int is_big_endian (void)
{
union {
unsigned short i;
unsigned char c[2];
} data;
data.i = 0x1234;
if (data.c[0] == 0x12)
return 1;
return 0;
}
int main (void)
{
if (is_big_endian ())
printf ("This is a big-endian system.\n");
else
printf ("This is a little-endian system.\n");
return 0;
}注意，上述代码段中的 is_big_endian 函数使用了 C 语言的联合类型，这种类型在处理这种形式的问题时具有非常好的便利性。
另外，我们希望在程序中可以根据目标系统的字节序自动完成额外的数据转换。这种转换通常就是互换字节中的值。为了完成这种转换，我们可以使用类似清单 2-1 中的程序来判断本机的字节序，然后根据要读取或者写入的目标字节序来完成相应的转换。但在实践当中，我们采用条件编译来完成这种字节序的判断：
#define _LIL_ENDIAN 1234
#define _BIG_ENDIAN 4321
#if defined(__i386__) || defined(__ia64__) || \
(defined(__alpha__) || defined(__alpha)) || \
defined(__arm__) || \
(defined(__CC_ARM) && !defined(__BIG_ENDIAN)) || \
(defined(__mips__) && defined(__MIPSEL__)) || \
defined(__LITTLE_ENDIAN__) || \
defined(WIN32)
#define _BYTEORDER _LIL_ENDIAN
#else
#define _BYTEORDER _BIG_ENDIAN
#endif程序可通过编译器预先定义的宏来判断目标平台是大头系统还是小头系统，然后将 _BYTEORDER 定义为相应的宏。然后在程序中采用下面的方法来处理字节序：
#if _BYTEORDER == _BIG_ENDIAN
/* for the big-endian system */
#else
/* for the little-endian system */
#endif比如，我们为了从文件中读取一个由小头系统保存的 16 位二进制整数，我们可以用下面的 C 代码编写程序：
unsigned short temp;
/* read back the data. */
read (fd, &temp, sizeof (unsigned short));
close (fd);
#if _BYTEORDER == _BIG_ENDIAN
temp = ((temp << 8)|(temp >> 8));
#endif上面的 temp = ((temp << 8)|(temp >> 8)); 语句将 temp 的高八位和低八位互换然后重新组合成了新的整数。
在使用 GNU C 函数库时，我们还可以在源程序中包含 <endian.h> 头文件，并通过该头文件中已经定义好的 __BYTE_ORDER 宏来帮助判断目标系统的字节序，比如：
#include <stdio.h>
#include <endian.h>
int main (void)
{
#if __BYTE_ORDER == __LITTLE_ENDIAN
printf ("This is a little-endian system\n");
#elif __BYTE_ORDER == __BIG_ENDIAN
printf ("This is a big-endian system\n");
#elif __BYTE_ORDER == __PDP_ENDIAN
printf ("This is a PDP-endian system\n");
#endif
return 0;
}清单 2-2 中的函数，给出了将内存中的大头或者小头整数转换为本机字节序的 C 语言例程（函数），可供读者参考或使用。
清单 2-2 将大头整数或者小头整数转换为本机字节序（conv_int.c)
static inline unsigned short ReadLE16Mem (const unsigned char** data)
{
unsigned short h1, h2;
h1 = *(*data); (*data)++;
h2 = *(*data); (*data)++;
return ((h2<<8)|h1);
}
static inline unsigned int ReadLE32Mem (const unsigned char** data)
{
unsigned int q1, q2, q3, q4;
q1 = *(*data); (*data)++;
q2 = *(*data); (*data)++;
q3 = *(*data); (*data)++;
q4 = *(*data); (*data)++;
return ((q4<<24)|(q3<<16)|(q2<<8)|(q1));
}
static inline unsigned short ReadBE16Mem (const unsigned char** data)
{
unsigned short h1, h2;
h1 = *(*data); (*data)++;
h2 = *(*data); (*data)++;
return ((h1<<8)|h2);
}
static inline unsigned int ReadBE32Mem (const unsigned char** data)
{
unsigned int q1, q2, q3, q4;
q1 = *(*data); (*data)++;
q2 = *(*data); (*data)++;
q3 = *(*data); (*data)++;
q4 = *(*data); (*data)++;
return ((q1<<24)|(q2<<16)|(q3<<8)|(q4));
}在 8 位以上的电子计算机中，处理器指令处理的往往是字、双字、四倍字而不是字节。比如在 32 位处理器中，加法指令要求操作数是 32 位的二进制数。但在随机访问存储器（RAM，亦称“内存”）中，数据以字节为单位存放。从电子计算机设计的角度出发，将 32 位二进制数在内存中保存在 4 倍地址上则可以获得最好的访问性能。比如在 32 位大头系统中，我们可以将 0x12345678 的起始字节 0x12 保存在地址为 0 的内存单元中，也可以保存在地址为 1 的内存单元中。如果将起始字节保存在 0、4、8 等地址上时，则处理器指令在访问这个 32 位二进制数时，就可以获得最大程度的优化性能。这种存放规则称为字节对齐（alignment）。甚至在某些处理器上，如果我们访问的操作数地址不是对齐的，处理器会抛出异常。
当我们使用高级编程语言编写程序时，通常不会遇到因为字节对齐而导致的问题。这是因为高级编程语言已经仔细设计并处理了可能出现的问题。但在使用汇编语言，或者比较低级的编程语言4，如 C 语言时，则经常会遇到字节对齐导致的问题。
对齐问题是许多接触 C 语言不多的开发人员常常忽略的问题。为了对对齐有个感性认识，我们首先看下面的代码：
#include <stdio.h>
void align_1 (void)
{
struct {
char c;
int i;
} my_struct;
printf ("The size of my_struct is %d\n", sizeof (my_struct));
}
int main (void)
{
align_1 ();
return 0;
}在编译并运行这段代码之前，读者可以首先推断一下该程序的正确输出。然后，我们在 PC 上运行这个程序看看它的实际结果：
user$ gcc -o align align.c
user$ ./align
The size of my_struct is 8许多人会对此结果有疑问，然而，如果我们不作任何的特殊设置，这个结构的大小的确是 8。为什么会这样呢？这是因为，在 32 位处理器上，在存放多字节操作数时，编译器会根据操作数的大小确保在内存空间中该操作数对齐于地址边界。比如在上面这个结构中，char c 成员是个单字节的成员，这个成员可被保存在任意的地址；而 int i 成员的大小是 4 字节，编译器就会确保将 i 保存在地址为 4 的倍数的位置上。因此，上述结构在内存中存储时，它的实际内存布局不是我们想象的 c 占用一个字节，然后立即是 4 个字节的 i，而是像图 2-5 那样。
图 2-5 my_struct 结构数组的内存布局
编译器这样做的目的有两个：
- 根据操作数的大小和地址对齐存放操作数，可确保对该操作数的二进制运算速度最快，这是硬件设计决定的。
- 某些处理器指令在处理不对齐的操作数时，会出现处理器异常，从而导致总线错误5。
依此类推，我们可以看到下面这个结构的大小也是 8：
struct {
char c;
short s;
int i;
} my_struct;另外，编译器通常会提供某种方法，以便取消定义结构时的成员对齐。在 gcc 中，我们可以用 __attribute__ ((packed)) 修饰词取消结构内部的成员对齐：
struct __attribute__ ((packed)) {
int i;
short s;
char c;
} my_struct;为了避免因为对齐给我们带来麻烦，有的情况下我们需要仔细编码以便确保程序的正确性。比如，下面的程序试图将内存中的一个 32 位整数值取出来：
unsigned int read_uint_from_mem (const unsigned char* data)
{
unsigned int u;
memcpy (&u, data, sizeof (unsigned int));
return u;
}这段程序看起来没有什么问题，我们甚至可以这样编码：
unsigned int read_uint_from_mem (const unsigned char* data)
{
unsigned int *u;
u = (unsigned int*)data;
return *u;
}然而，上面的两个程序段，当传入的 data 地址不在 4 字节边界上对齐的时候，就会出现问题。读者可以在 PC 或者某些 RTOS（如 uC/OS）上测试上面的程序段，用下面的方式调用：
unsigned char data [1024];
unsigned int u;
u = read_uint_from_mem (data + 1);
我们会发现，在某些实时操作系统（RTOS，如 uC/OS）上，上述代码会给出总线错误，从而导致程序异常退出。正确的 read_uint_from_mem 函数应该如下设计，才能确保避免因为对齐造成的程序错误：
unsigned int read_uint_from_mem (const unsigned char* data)
{
unsigne int q1, q2, q3, q4;
q1 = data[0];
q2 = data[1];
q3 = data[2];
q4 = data[3];
return ((q1<<24)|(q2<<16)|(q3<<8)|(q4));
}
那么，一样的代码，为何在 Windows 和 Linux 等操作系统上运行就不会出错呢？这是因为 Windows 和 Linux 内核运行在具有 MMU 单元的处理器上，采用的是虚拟内存技术。当指令在非对齐的内存地址上访问整数值时，处理器将产生一个陷阱（trap），Linux 内核会捕捉该陷阱，并恰当处理由于非对齐产生的问题，从而可以让应用程序正常运行下去。有关细节，将在本书第七篇“操作系统”中讲述。读者亦可参阅其他讲述操作系统的书籍。
二进制逻辑运算就是比特位的逻辑运算。当两个字节、字或双字等（以下简称“操作数”）进行二进制逻辑运算时，对应位上的比特参与运算，和其他位没有关系。常见的逻辑运算有如下取反、或、与、异或等四种。
取反。该运算针对单个操作数进行处理，顾名思义，该运算对操作数的每个比特位做取反操作，亦即将 0 变成 1，将 1 变成 0。取反操作是单目运算，通常使用“~”运算符表示。比如，~0xFF 的结果是 0x00。
或。该运算是双目运算，两个操作数上的对应比特位的值做“或”运算，亦即只要其中有一个比特位的值是 1，则结果为 1，否则结果为 0。或运算通常使用“|”运算符表示。比如，0xF0 | 0x0F 的结果是 0xFF。
与。该运算是双目运算，两个操作数上的对应比特位的值做“与”运算，亦即当两个比特位的值都是 1 时结果 1，否则结果为 0。或运算通常使用“&”运算符表示。比如，0xF0 & 0x0F 的结果是 0x00。
异或。该运算是双目运算，两个操作数上的对应比特位的值做“异或”运算，亦即当两个比特位不同时结果1，否则结果为 0。异或运算通常使用“^”运算符表示。比如，0xF0 ^ 0x0F 的结果是 0xFF。异或运算有两个比较特殊的特性，一个是归零，即 A^A=0；一个是自反，即 A^B^B=A。前者可用于程序优化，比如在汇编程序中，可用来将某寄存器的值归零，而避免采用赋值操作（赋值操作通常需要一条额外的指令来完成）；后者可用于简单的加解密程序。
移位操作就是针对二进制数执行整体左移或者整体右移给定位数的操作，使用“<<”或者“>>”运算符表示。比如：0xF0 >> 4 的结果是 0x00。在汇编级别，大部分处理器支持自定义移位操作后空出来的位填充 0 还是 1。在高级编程语言中，通常补 0。
根据数学法则，对任意二进制数执行左移一位操作，就相当于乘以 2；执行右移一位操作就相当于除以 2。需要注意的是，这个法则实际上是通用的，比如对十进制的表达，左移一位就相当于乘以 10。因此，移位操作也经常用来优化计算，尤其是对整数的乘 2 和除 2 这种运算。另外还要注意的是，左移情形下最高位会丢失，右移情形下最低位（余数）会丢失。
尽管二进制在计算机中非常基础，但大部分程序基本上无需或很少需要直接进行二进制的操作和运算。二进制数的许多特性，比如使用逻辑门来组成加法器，被直接设计到了计算机或通信设备的物理层面，也就是说，计算机或通信设备的物理器件会更多使用基础的二进制操作。
在我们平常的编程工作中，二进制运算通常应用于不多的几个场景。其中最为常见的是单个字节序列和多字节数据（字、双字等）的相互转换。比如，我们要将两个字节合并为一个字，则可以使用如下的伪代码：
WORD high_half_word = 0x12
WORD low_half_word = 0x34
high_half_word = high_half_word << 8
WORD my_word = high_half_word + low_half_word
执行上述伪代码程序之后，my_word 的值将为 0x1234。当然，我们还可以将这个功能写成一个函数（或例程），如：
FUNCTION WORD assemble_word (BYTE high_byte, BYTE low_byte)
WORD high_half_word = high_byte
RETURN (high_half_word << 8) | low_byte
上面两个伪代码片段在实现同一功能时有稍许的不同。前者先将两个字节从字节数组中取出并分别赋值给了两个字变量（high_half_word 和 low_half_word），然后使用加运算获得了最终的字；后者使用了或运算。但无论如何，两段代码均使用了移位操作将低位字节左移 8 位后赋值给了 high_half_word 变量。另外，后者没有使用 low_half_word 变量，这是因为伪代码会根据其他操作数的类型自动执行类型转换，这里就是将 BYTE 类型转换为 WORD 类型，新的 WORD 变量的低八位来自 BYTE 变量，高八位填充 0。
需要说明的是，前一段代码更贴近于最终的计算机指令执行情况。尽管后一段代码更加短小，但最终在计算机上执行的指令也会展开成前一段代码那样去执行。
类似地，我们可以编写将字、双字等多字节数据解开成字节序列的代码，如：
FUNCTION BYTE, BYTE disassemble_word_a (WORD word)
low_half_byte = (BYTE)(word & 0x00FF)
high_half_byte = (BYTE)((word >> 8)) & 0x00FF)
RETURN high_half_byte, low_half_byte
上面的 disassemble_word_a 函数将给定的字 word 解开成两个字节并返回。
我们也可以通过字节数组来实现类似的功能，但需要注意的是，使用字节数组时，就牵涉到前述的字节序问题了。比如：
FUNCTION BYTE[] disassemble_word_b (WORD word)
BYTE[] bytes
bytes[0] = (BYTE)word
bytes[1] = (BYTE)(word >> 8)
RETURN bytes
上面的 disassemble_word_b 函数最终返回的字节数组中，低地址包含 word 的低八位，高地址包含高八位，也就是说，其字节序按小头进行了处理。另外，disassemble_word_b 和之前的 disassemble_word_a 函数还有一个区别是没有做“与”操作，这是因为从 WORD 类型转换为 BYTE 类型时，仅会保留低八位数据；也就是说，disassemble_word_a 函数中的“与”操作其实是多余的。
另外一个二进制运算的典型应用场合是将比特位作为标志（flag）使用，某个特定的比特位为 1 时，表明对应的判定为真，反之，特定的比特位为 0 时，表明对应的判定为假。比如我们一共有八个小篮子，每个篮子里边可以放一个鸡蛋，现在要随机放入或取走一个鸡蛋，可能连续有几次要放入鸡蛋，或者连续几次要取走鸡蛋，执行多次操作之后，有些篮子里边有鸡蛋而有些篮子里边没有鸡蛋。要快速确定哪些篮子是空的或者有鸡蛋，我们可以使用一个字节来表示篮子的使用情况，字节中的每个比特位表示对应的篮子里边是否有鸡蛋，比如第 0 位标识编号为 0 的篮子。现在想要取走一个鸡蛋，要想知道哪个篮子里边有鸡蛋，可以使用下面的函数：
FUNCTION BYTE first_true_bit_a (BYTE byte)
IF (byte & 00000001b)
RETURN 0
IF (byte & 00000010b)
RETURN 1
IF (byte & 00000100b)
RETURN 2
IF (byte & 00001000b)
RETURN 3
IF (byte & 00010000b)
RETURN 4
IF (byte & 00100000b)
RETURN 5
IF (byte & 01000000b)
RETURN 6
IF (byte & 10000000b)
RETURN 7
RETURN 0xFF
上面的 first_true_bit_a 函数非常啰嗦，其实我们可以循环语句来编写：
FUNCTION BYTE first_true_bit_b (BYTE byte)
BYTE[]indexes = [0, 1, 2, 3, 4, 5, 6, 7]
BYTE idx
FOR idx IN indexes
# FOR idx IN RANG (0, 7)
IF (byte & (0x01 << idx))
RETURN idx
RETURN 0xFF
注意，上面的两个函数在没有找到有鸡蛋的篮子时，会返回 0xFF（十进制的 255）。上面这个函数还可以不使用 indexes 字节数组，而使用如下的方式编写：
FUNCTION BYTE first_true_bit_c (BYTE byte)
BYTE idx = 0
WHILE (idx < 8)
IF (byte & (0x01 << idx))
RETURN idx
idx = idx + 1
RETURN 0xFF
当然，要解决上面的鸡蛋篮子问题，也可以使用字节数组来表示对应篮子是空的还是有鸡蛋的。使用比特位则可以节省空间的使用，这种技巧在存储空间比较紧张的系统中经常使用。
另外一个二进制运算的典型应用场合是字符集编码的处理，可用来判断特定的字节序列是否是一个有效的字符。详情请见本篇第 4 章“文字：字符集及编码”。
在二进制数据的传输或存储过程中，经常会遇到因为各种干扰或硬件失效而导致的数据丢失或损坏问题。此时，最有效的解决办法就是增加所传输数据的冗余量，从而可以根据数据的冗余信息恢复数据，本书第 X 章“”提到的磁盘阵列技术是最典型的用例。另外一些情形下，我们只需要知道数据的传输是否正确，如果不正确，可以要求对方再次传输。此时，我们可以在数据中增加一些专门用于校验数据正确性的校验码来解决这个问题。
一个最简单的校验方式就是奇偶校验。奇偶校验计算所传输的每个字节中位值为 1 的比特位个数，如果该个数是奇数，则校验位为 1，如果个数是偶数，则校验位为 06。这样，可以在一定概率7基础上判断传输的正确性。通常，使用一个字节的最高位作为校验位，其余低七位包含了真正的数据。针对这里描述的奇偶校验方法，要判断一个收到的字节是否在传输过程中出现问题，则只需要计算该字节中位值为 1 的比特位（简称“真比特位”）个数，如果结果是偶数，可认为是正确的，否则需要重新传输8。
如下函数计算给定字节中真比特位的个数：
FUNCTION BYTE get_nr_true_bits (BYTE byte)
BYTE idx = 0
BYTE count = 0
WHILE (idx < 8)
IF (byte & (0x01 << idx))
count = count + 1
idx = idx + 1
RETURN 0xFF
上面这个函数可以正常工作，但每次调用需要八次循环才能获得结果。我们可以考虑使用查表法来优化这个函数，也就是说，将可能的值事先计算好，然后直接返回对应数组中的单元就可以了。基于此优化方法，我们可以将这个函数优化为只有下面两行代码：
FUNCTION BYTE get_nr_true_bits (BYTE byte)
CONST BYTE[] counts = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]
RETURN counts [byte & 0x0F] + counts [byte >> 4 & 0x0F]
注意，我们只保存了值从 0 到 0x0F（0~15）这十六个字节的真比特位个数，然后将一个字节分成了两半分别查询对应的真比特位个数，最终返回这两个个数的和。
在使用时，数据的发送端可调用上面的函数生成包含偶校验位（最高位）的字节（调用前，字节的最高位必须为 0，真正的数据仅包含在低七位）：
BYTE count = get_nr_true_bits (my_byte)
IF (count & 0x01)
my_byte = my_byte | 0x40
...
接收端可如下调用上述函数完成偶校验：
BYTE count = get_nr_true_bits (my_byte)
IF (count & 0x01)
RETURN FALSE
...
在上面的使用代码中，通过和 0x01 相与，即可判断 count 变量的奇偶性。
奇偶校验其实是循环冗余校验（CRC，cyclic redundancy check）方法的一种特列。循环冗余校验在通信领域使用较多，我们可以将 CRC 算法看成是散列（哈希，hash）函数，其基本思想是将传输的数据当做一个位数很长的二进制数，将这个数除以另一个数，所得到的余数作为该数据的校验码。有关散列函数和 CRC 算法的详情，读者可参阅本书第 12 章“压缩及加密”。在其他的散列和加解密算法中，也经常使用各种二进制位运算，某些是算法本身利用了二进制算术的一些特性，某些则利用二进制做性能优化。
通常在 32 位电子计算机上，每条指令操作的数据是双倍字，而在 64 位电子计算机上，每条指令操作的数据是四倍字。如果在 32 位或 64 位计算机上，让每条指令仅处理一个字节，将会导致计算能力的浪费，或者反过来想，我们可以在一些情况下，将处理字节的算法组合成双倍字或者四倍字来进行处理，从而充分利用计算机的处理能力。这一优化思想在图形学中尤其有用。
计算机屏幕上的每个点一般使用红绿蓝（RGB）三种颜色来表示，称为颜色分量，取值范围一般为 0x00~0xFF，可表达 224 种颜色。针对不同的颜色分量取不同的值，就可以表示不同的颜色。有关详情，读者可参阅本书第五篇“信息的计算机展现”中的相关章节。
在计算图形学中，我们经常需要进行像素的混合运算。比如给定两个像素，各取两个像素当中 RGB 分量的一半形成结果像素，就实现了半透明效果。在程序中，RGB 三个颜色分量可使用 32 位二进制双倍字来表示，低八位表示B分量、八位到十六位表示 G 分量，十六位到二十四位表示 R 分量9。要计算上面的半透明混合效果下的结果像素，可使用下面的代码：
FUNCTION DWORD blend_pixels (DWORD p1, DWORD p2)
DWORD b1 = (p1 & 0xFF)
DWORD g1 = (p1 >> 8) & 0xFF
DWORD r1 = (p1 >> 16)& 0xFF
DWORD b2 = (p2 & 0xFF)
DWORD g2 = (p2 >> 8) & 0xFF
DWORD r2 = (p2 >> 16)& 0xFF
b1 = (b1 >> 1) | (b2 >> 1)
g1 = (g1 >> 1) | (g2 >> 1)
r1 = (r1 >> 1) | (r2 >> 1)
RETURN (r1 << 16) | (g1 << 8) | b1
上面的 blend_pixels 函数使用位运算替代了乘法和加法运算，速度将相当快，但只能适用于一半一半的透明效果情况下。当我们要实现一个像素 1/3 另一个像素 2/3 的半透明混合效果时，则无法使用这个方法，此种情况下的代码如下：
FUNCTION DWORD blend_pixels_with_alpha (DWORD p1, DWORD p2, BYTE alpha)
DWORD b1 = (p1 & 0xFF)
DWORD g1 = (p1 >> 8) & 0xFF
DWORD r1 = (p1 >> 16)& 0xFF
DWORD b2 = (p2 & 0xFF)
DWORD g2 = (p2 >> 8) & 0xFF
DWORD r2 = (p2 >> 16)& 0xFF
b1 = (b1 * alpha/255) | (b2 * (255-alpha)/255)
g1 = (g1 * alpha/255) | (g2 * (255-alpha)/255)
r1 = (r1 * alpha/255) | (r2 * (255-alpha)/255)
RETURN (r1 << 16) | (g1 << 8) | b1
注意在上面的 blend_pixels_with_alpha 函数中，我们使用取值范围为 0~xFF 的 Alpha 值来确定结果像素中第一个像素的作用大还是第二个像素的作用大。读者可以将 Alpha 值看作是一个权重参数。在更加一般的图形库（比如 OpenGL 中），通常使用 0~1 之间的实数来表示该权重。因为使用了整数的乘法和除法运算（或者实数的乘除运算），
blend_pixels_with_alpha 函数的性能显然要远远低于上面的 blend_pixels 函数。
根据前述的优化思想，我们可以在 64 位系统上对该函数做适当的优化，其核心思想是将 RGB 三分量扩展到 64 位四倍字中进行计算，将上面的三次乘除运算简化为一次乘除运算。如下所示：
FUNCTION DWORD blend_pixels_on_64bit (DWORD p1, DWORD p2, BYTE alpha)
BYTE b1 = (p1 & 0xFF)
BYTE g1 = (p1 >> 8) & 0xFF
BYTE r1 = (p1 >> 16)& 0xFF
BYTE b2 = (p2 & 0xFF)
BYTE g2 = (p2 >> 8) & 0xFF
BYTE r2 = (p2 >> 16)& 0xFF
QWORD qp1 = (r1 << 32) | (g1 << 16) | b1
QWORD qp2 = (r2 << 32) | (g2 << 16) | b2
qp1 = (qp1 * alpha/255) + (qp2 * (255-alpha)/255)
b1 = (qp1 & 0xFF)
g1 = (qp1 >> 16) & 0xFF
r1 = (qp1 >> 32)& 0xFF
RETURN (r1 << 16) | (g1 << 8) | b1
以上优化的思路是，将8位的 RGB 分量在 64 位四倍字中扩展为 16 位（高八位取0），然后进行 Alpha 混合计算。扩展到 16 位的目的是，在进行 alpha 有关的乘法运算时，不会导致溢出。最后再从结果四倍字中取出 RGB 分量并组装成 32 位的 RGB 像素值返回。 当我们使用 C 语言实现上述函数时，我们还可以充分利用 C 语言的直接访问地址能力，快速分解和组装像素，这体现了 C 语言的优势。如下所示（注意该代码仅适用于 64 位系统）：
typedef BYTE unsigned char;
typedef UINT32 unsigned int;
typedef UINT64 unsigned long;
UINT32 blend_pixels_on_64bit (UINT32 p1, UINT32 p2, BYTE alpha)
{
BYTE* pp1 = (BYTE*)(&p1);
BYTE* pp2 = (BYTE*)(&p2);
UINT64 qp1 = 0, qp2 = 0;
BYTE *pqp1 = (BYTE*)&qp1, *pqp2 = (BYTE*)&qp2;
pqp1[0] = pp1[0];
pqp1[2] = pp1[1];
pqp1[4] = pp1[2];
pqp2[0] = pp2[0];
pqp2[2] = pp2[1];
pqp2[4] = pp2[2];
qp1 = ((qp1 * alpha) >> 8) + ((qp2 * (255-alpha)) >> 8);
pp1[0] = pqp1[0];
pp1[1] = pqp1[2];
pp1[2] = pqp1[4];
return p1;
}注意在上面的 C 代码中，我们还将除以 255 的运算用右移 8 位的操作替代（尽管有误差，但可以接受）。我们还可以将这条语句写成下面这种形式：
qp1 = (qp1 * alpha + (qp2 * (255-alpha))) >> 8;
许多读者可能会担心上面的优化会导致扩展后的 RGB 16 位分量在执行加法运算后溢出，但在这种情况下应该不会发生此种情形。
通过上面的优化，对此类问题我们可以实现某种程度上的并行计算。类似地，我们也可以在 32 位系统上针对 16 位颜色深度做类似的优化。
Footnotes
-
数据来源于维基百科。 ↩
-
除非程序使用文中所明示的特定编程语言给出，否则本书中的程序均使用伪代码。本书所使用伪代码的语法见本书附录A。 ↩
-
我们说某种编程语言是低级编程语言，并不是说这种编程语言不好，而是指这种编程语言离处理器指令集较为接近。最低级的编程语言当属汇编语言。 ↩
-
在支持虚拟内存的操作系统，比如 Linux 中，因为内核会捕捉这种处理器异常并作适当的处理，从而在不支持虚拟内存的 RTOS 系统上，对齐问题的表现却很明显。 ↩
-
这里描述的奇偶校验方法中的校验位称为“偶校验位”。使用偶校验位时，可确保包括校验位在内的所有位值为 1 的比特位个数是偶数。与之相反的就是“奇校验位”。另外，当所传输的数据位出现偶数位失效（比如有两个比特位从 1 变成 0）的情况下，奇偶校验并不能有效侦测错误。 ↩
-
差不多是 50%。 ↩
-
实践当中，奇偶校验以及下面介绍的循环冗余校验，都由计算机的电子物理器件完成，上层软件基本不需要做相应的处理。 ↩
-
这是颜色深度为 32 位的情形下的像素分量表示方式，在颜色深度为 16 位情形下，RGB 三个分量分别占用 5、6、5 比特位。详情见第五篇“信息的计算机展现”。 ↩