位操作

位操作是程序设计中对位数组或二进制数的一元和二元操作。在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。在现代架构中，位运算的运算速度通常与加法运算相同（仍然快于乘法运算），但是通常功耗较小，因为资源使用减少。^[1]

位运算符

下面的解释中，任何二进制位的表示都从右侧（最低位）开始计数，向左进。举个例子，二进制值0001（十进制1）除第一位（即最右边）每位上都是0。

取反（NOT）

参见：一補數

取反是一元运算符，对一个二进制数的每一位执行逻辑反操作。使数字1成为0，0成为1。例如：

NOT 0111（十進位7） = 1000（十進位8） 

NOT 10101011 (十进制 171) = 01010100 (十进制 84) 

结果等于该值的补码减一。如果使用补码算术，则 NOT x = -x − 1。

对于无符号整数，数的按位补码是其在无符号整数范围的中点另一边的“镜像”。例如，对于8位无符号整数，NOT x = 255 - x，可以在图上将其可视化为一条向下的线，相当于把从 0 到 255 递增的范围，“翻转”到从 255 到 0 递减的范围。一个简单而有说明性的使用例子是反转灰度图像，其中每个像素存储为无符号整数。

许多程序设计语言（包括C语言家族），取反操作符用波浪线"~"表示。值得注意的是此操作符与“逻辑非（!）”操作符不同。在C++中，逻辑非将数字整体看做一个布尔类型——将真值转化为假，将假值转化为真；而C语言将0转化为1，将非零值转化为0。“逻辑非”并不是一个位操作。

 

4位整数按位或

按位或（OR）

按位或处理两个长度相同的二进制数，两个相应的二进位中只要有一个为1，该位的结果值就为1。例如

 0101（十进制5） OR 0011（十进制3） = 0111（十进制7） 

在C类程序设计语言中，按位或操作符是"|"。这一操作符需要与逻辑或运算符（||）区别开来。

按位或能够将每一位看做旗标；在二进制数中的每一位可以表示不同的布尔变量。应用按位或操作可以将二进制数的某一位设为1。例如

0010（十进制2） 

能够看做包含4个旗标的组合。第1，2，4旗标为0；第3个旗标为1。利用按位或可以将第1个旗标设置为1，而其他旗标不变。

 0010（十进制2） OR 1000（十进制8） = 1010（十进制10） 

这一技巧通常用来保存程序中的大量布尔变量。

 

4位整数按位异或

按位异或（XOR）

按位异或运算，对等长二进制模式或二进制数的每一位执行逻辑异或操作。操作的结果是如果某位不同则该位为1，否则该位为0。例如

 0101 XOR 0011 = 0110 

在类C语言中，按位异或运算符是"^"。

汇编语言的程序员们有时使用按位异或运算作为将寄存器的值设为0的捷径。用值的自身对其执行按位异或运算将得到0。并且在许多架构中，与直接加载0值并将它保存到寄存器相比，按位异或运算需要较少的中央处理单元时钟周期。

按位异或也可以用于在比特集合中切换旗标。给出一个比特模式，

0010 

第一和第三位能够通过按位异或运算使用同时切换。

 0010 XOR 1010 = 1000 

这一技巧可用于操作表示布尔变量的比特模式。

 

4位整数按位与

按位与（AND）

按位与处理两个长度相同的二进制数，两个相应的二进位都为1，该位的结果值才为1，否则为0。例如：

 0101 AND 0011 = 0001 

此操作可以被用来检查一个特定的位是1还是0。例如，给定一个二进制模式0011（十进制3），我们用按位与和一个仅在第二位为1的二进制模式来确定第二位是否为1：

 0011 (十进制 3) AND 0010 (十进制 2) = 0010 (十进制 2) 

因为结果0010是非零的，所以我们知道原模式中的第二位是1。这通常被称为位掩码。（类似的，使用纸胶带覆盖不应更改的部分或不感兴趣的部分。在这种情况下，0 值会屏蔽不感兴趣的位。）

按位与可用于清除寄存器的选定位（或旗标），其中每个位代表一个单独的布尔状态。 这种技术是一种使用尽可能少的内存来存储大量布尔值的有效方法。

例如，0110（十进制 6）可以被认为是一组四个旗标，其中第一个和第四个旗标是清除 (0)，第二和第三个旗标是设置 (1)。 第三个旗标可以通过按位与仅在第三位具有零的模式来清除：

 0110 (十进制 6) AND 1011 (十进制 11) = 0010 (十进制 2) 

因为这条性质，通过查询最低位的值检查一个二进制数的奇偶性变得容易。用以上的例子：

 0110 (十进制 6) AND 0001 (十进制 1) = 0000 (十进制 0) 

因为6按位与1是0，6可以被2整除，所以6是偶数。

在类C语言中，按位与用'&'表示。

数学等价物

假设${\displaystyle x\geq y}$ ，对于非负整数，按位运算可以被写成如下形式：

${\displaystyle {\begin{aligned}\operatorname {NOT} x&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+1\right){\bmod {2}}\right]=2^{\left\lfloor \log _{2}(x)\right\rfloor +1}-1-x\\x\operatorname {AND} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\\x\operatorname {OR} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right]{\bmod {2}}\right)\\x\operatorname {XOR} y&=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left(\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right]{\bmod {2}}\right)=\sum _{n=0}^{\lfloor \log _{2}(x)\rfloor }2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor +\left\lfloor {\frac {y}{2^{n}}}\right\rfloor \right){\bmod {2}}\right]\end{aligned}}}$ 

所有二元逻辑运算符的真值表

两个二进制变量（英语：Binary data）有16种可能的真值函数；这定义了一个真值表。

这是两位 P 和 Q 的按位等效运算：

p	q		矛盾^0	逻辑或非^1	逆非蕴含（英语：Converse nonimplication）^2	非p^3	实质非蕴涵^4	非q^5	逻辑异或^6	逻辑与非^7		逻辑与^8	逻辑异或非（英语：Logical biconditional）^9	q（英语：Projection (set theory)）^10	实质条件^11	p（英语：Projection (set theory)）^12	逆命题^13	逻辑或^14	恒真式^15
1	1		0	0	0	0	0	0	0	0		1	1	1	1	1	1	1	1
1	0		0	0	0	0	1	1	1	1		0	0	0	0	1	1	1	1
0	1		0	0	1	1	0	0	1	1		0	0	1	1	0	0	1	1
0	0		0	1	0	1	0	1	0	1		0	1	0	1	0	1	0	1
按位 等效			0	NOT (p OR q)	(NOT p) AND q	NOT p	p AND (NOT q)	NOT q	p XOR q	NOT (p AND q)		p AND q	NOT (p XOR q)	q	(NOT p) OR q	p	p OR (NOT q)	p OR q	1

移位

移位是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。在类C语言中，左移使用两个小于符号"<<"表示，右移使用两个大于符号">>"表示。

位寻址

 

算术左移

 

算术右移

如果寄存器的宽度（通常为 32 甚至 64）大于最小可寻址单元（通常称为字节）的位数（通常为 8），则移位操作会促使从字节到位的寻址策略。因此，进位制的标准数字书写中，取“左”和“右”方向，使得左移增加数字的值，右移减少数字的值——如果先读取左侧数位，这就是大端字节序。忽略寄存器两端的边界效应，算术和逻辑移位操作的行为相同，移动 8 位将位模式转移 1 个字节位置，方式如下：

• 小端序：左移 8 个位置，字节地址加 1；右移 8 个位置，字节地址减 1。
• 大端序：左移 8 个位置，字节地址减 1；右移 8 个位置，字节地址加 1。

算术移位

主條目：算術移位

在算术移位中，溢出两端的位都被丢弃。算术左移中，右侧补上0；算术右移中，左侧补上符号位（英语：Sign bit）（补码中的最高位），以保持原数的符号不变。

这个例子使用一个8位寄存器，解释为补码：

 00010111 (十进制 +23) LEFT-SHIFT = 00101110 (十进制 +46) 

 

逻辑左移

 

逻辑右移

 10010111 (十进制 −105) RIGHT-SHIFT = 11001011 (十进制 −53) 

在第一种情况下，最左边的数字被移到寄存器的末尾，新的 0 被移到最右边的位置。 在第二种情况下，最右边的 1 被移出（可能进入了进位标志（英语：Carry flag）），一个新的 1 被复制到最左边的位置，保留了数字的符号。 多个移位有时会缩短为一个移位，减少了几位。 例如：

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO = 01011100 (decimal +92) 

算术左移n位等价与乘以2ⁿ (前提值没有整数溢出）。一个补码的值算术右移n 位等价与除以2ⁿ 下取整。如果二进制数被视为一的补码，则相同的右移运算会导致除以2ⁿ 和向零舍入。

逻辑移位

应用逻辑移位时，移位后空缺的部分全部填0。因此，逻辑左移和算术左移完全相同。

但是，由于逻辑右移将值 0 位插入最高位，而不是复制符号位，因此它适用于无符号二进制数，而算术右移适用于有符号补码二进制数。

 0001（十进制1） << 3（左移3位） = 1000（十进制8） 

 1010（十进制10） >> 2（右移2位） = 0010（十进制2） 

循环移位

另一种移位是循环移位。

 

循环左移或旋转

 

循环右移或旋转

旋转

在此操作中，有时称为循环无进位，位被“旋转”，就好像寄存器的左端和右端连接在一起一样。 在左移期间移入右侧的值是从左侧移出的任何值，右移操作时反之亦然。 如果需要保留所有现有位，这很有用，并且它经常用于数字密码学中。

 

进位左旋

 

进位右旋

进位旋转

进位旋转是一种旋转操作的变种，其中移入（在任一端）的位是进位标志的旧值，移出的位（在另一端）成为进位标

志的新值。

一个简单的进位旋转可以模拟逻辑和算术移位，只需提前设置好进位标志。比如，如果进位标志是0，那么x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE是逻辑右移一位；如果进位标志里是符号位的拷贝，那么x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE是算术右移一位。因为这些原因，一些微控制器像低端PIC微控制器只有旋转和进位旋转，并不担心算术或逻辑移位。

当对大于处理器的本机字长的数字执行移位时，进位旋转特别有用，因为如果一个大数存储在两个寄存器中，从第一个寄存器的一端移出的位必须在另一端进入第二个寄存器。使用循环进位时，该位在第一次移位期间“保存”在进位标志中，准备在第二次移位期间移入而无需任何额外准备。

在高级语言中

类C语言和Python

在類C語言和Python中，逻辑移位运算符是左移“<<”和右移“>>”。移位的位置数作为运算符的第二个参数给出。例如，

x = y << 2; 

将x赋值为y左移两位的结果，其等价于乘以四。

移位可能导致实现定义的行为或未定义行为，因此在使用它们时必须小心。 在 C 和 C++ 中，移位大于或等于字大小的位数是未定义的行为。^[2]右移负值是实现定义的，但良好的编码实践不建议这样做；^[3]如果结果无法在结果类型中表示，则左移有符号值的结果是未定义的。^[4]

在 C# 中，当第一个操作数是整形或长整形时，右移是算术移位。 如果第一个操作数是无符号整形或无符号长整形，则右移是逻辑移位。^[5]

Java

JAVA中有一个特有的无符号右移操作符“>>>”。此操作将忽略操作数的符号，同样的还有“>>>=”。

JavaScript

JavaScript使用按位运算将两个或多个数字中的每一个求值为 1 或 0。^[6]

Pascal

在 Pascal 及其所有方言中（如 Object Pascal 和 Standard Pascal（英语：GNU Pascal）），逻辑左移运算符和右移运算符分别是“shl”和“shr”。 即使对于有符号整数， shr 的行为也类似于逻辑移位，并且不会复制符号位。 要移动的位置数作为第二个参数给出。 例如，下面将 y 左移两位的结果赋值给 x：

x := y shl 2; 

其他

• 汉明权重，在密码学中被使用
• 计数前导零（英语：Count leading zeros）

应用

位运算是必要的，尤其是在设备驱动程序、低级图形、通信协议包组装和解码等低级编程中。

尽管机器通常具有执行算术和逻辑运算的有效内置指令，但所有这些运算都可以通过以各种方式组合按位运算符和零测试来执行。^[7]例如，这里是古埃及乘法（英语：Ancient Egyptian multiplication）的伪代码实现，展示了如何仅使用位移和加法将两个任意整数 a 和 b（a 大于 b）相乘：

c ← 0 while b ≠ 0  if (b and 1) ≠ 0  c ← c + a  left shift a by 1  right shift b by 1 return c 

另一个例子是加法的伪代码实现，展示了如何使用按位运算符和零测试计算两个整数 a 和 b 的和：

while a ≠ 0  c ← b and a  b ← b xor a  left shift c by 1  a ← c return b 

参考

1. CMicrotek Low-power Design Blog. CMicrotek. [2015-08-12]. （原始内容于2015-08-20）. 
2. Arithmetic operators - cppreference.com. en.cppreference.com. [2016-07-06]. （原始内容于2022-08-08）. 
3. INT13-C. Use bitwise operators only on unsigned operands. CERT: Secure Coding Standards. Software Engineering Institute, Carnegie Mellon University. [2015-09-07]. （原始内容于2016-04-22）. 
4. JTC1/SC22/WG14 N843 "C programming language" （页面存档备份，存于互联网档案馆）, section 6.5.7
5. Operator (C# Reference). Microsoft. [2013-07-14]. （原始内容于2017-07-06）. 
6. "JavaScript Bitwise" （页面存档备份，存于互联网档案馆）. W3Schools.com.
7. Synthesizing arithmetic operations using bit-shifting tricks. Bisqwit.iki.fi. 2014-02-15 [2014-03-08]. （原始内容于2014-03-08）.