查看“︁位操作”︁的源代码

{{Multiple issues|
{{Expert|time=2010-08-10T13:27:59+00:00|subject=计算机科学}}
{{Refimprove|time=2023-09-28T08:00:22+00:00}}
{{Expand|time=2010-08-10T13:27:59+00:00}}

}}
{{NoteTA
|T=zh-cn:位操作;zh-tw:位元運算;
|G1 = IT
|G2 = Electronics
|1 = zh-cn:取反; zh-tw:反相;
}}
'''位操作'''是[[程序设计]]中对[[位数组]]或[[二进制|二进制数]]的一元和二元操作。在许多古老的[[微处理器]]上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。在现代架构中，位运算的运算速度通常与加法运算相同（仍然快于乘法运算），但是通常功耗较小，因为资源使用减少。<ref>{{Cite web |title=CMicrotek Low-power Design Blog |url=http://cmicrotek.com/wordpress_159256135/ |publisher=CMicrotek |access-date=2015-08-12 |archive-date=2015-08-20 |archive-url=https://web.archive.org/web/20150820011419/http://cmicrotek.com/wordpress_159256135/ |dead-url=no }}</ref>

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

=== 取反（NOT） ===
{{参见|一補數}}
'''取反'''是[[一元運算|一元运算符]]，对一个二进制数的每一位执行[[逻辑非|逻辑反]]操作。使数字1成为0，0成为1。例如：
 NOT '''0'''111（十進位7）
   = '''1'''000（十進位8）

 NOT 10101011  (十进制 171)
   = 01010100  (十进制 84)
结果等于该值的[[二補數|补码]]减一。如果使用补码算术，则 <code>NOT x = -x − 1</code>。

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

许多程序设计语言（包括[[C语言]]家族），取反操作符用波浪线"<code>~</code>"表示。值得注意的是此操作符与“逻辑非（<code>!</code>）”操作符不同。在C++中，逻辑非将数字整体看做一个[[布林 (資料類型)|布尔类型]]——将真值转化为假，将假值转化为真；而C语言将0转化为1，将非零值转化为0。“逻辑非”并不是一个位操作。
[[File:0...15 OR.svg|alt=thumb|thumb|4位整数按位或]]

=== 按位或（OR） ===
'''按位或'''处理两个长度相同的二进制数，两个相应的二进位中只要有一个为1，该位的结果值就为1。例如
 -{}-   0'''101'''（十进制5）
 OR 0'''011'''（十进制3）
  = 0'''111'''（十进制7）

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

按位或能够将每一位看做[[旗標|旗标]]；在二进制数中的每一位可以表示不同的布尔变量。应用按位或操作可以将二进制数的某一位设为1。例如
 -{}-0010（十进制2）

能够看做包含4个旗标的组合。第1，2，4旗标为0；第3个旗标为1。利用按位或可以将第1个旗标设置为1，而其他旗标不变。
 -{}-   0010（十进制2）
 OR 1000（十进制8）
  = 1010（十进制10）

这一技巧通常用来保存程序中的大量布尔变量。
[[File:Z2^4; Cayley table; binary.svg|alt=thumb|thumb|4位整数按位异或]]

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

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

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

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

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

这一技巧可用于操作表示布尔变量的比特模式。
[[File:0...15 AND.svg|alt=thumb|thumb|[[4位元|4位]]整数按位与]]

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

此操作可以被用来检查一个特定的位是1还是0。例如，给定一个二进制模式0011（十进制3），我们用按位与和一个仅在第二位为1的二进制模式来确定第二位是否为1：
     00'''1'''1 (十进制 3)
 AND 00'''1'''0 (十进制 2)
   = 00'''1'''0 (十进制 2)
因为结果0010是非零的，所以我们知道原模式中的第二位是1。这通常被称为''位掩码''。（类似的，使用[[紙膠帶|纸胶带]]覆盖不应更改的部分或不感兴趣的部分。在这种情况下，0 值会屏蔽不感兴趣的位。）

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

例如，0110（十进制 6）可以被认为是一组四个旗标，其中第一个和第四个旗标是清除 (0)，第二和第三个旗标是设置 (1)。 第三个旗标可以通过按位与仅在第三位具有零的模式来清除：
     0'''1'''10 (十进制 6)
 AND 1'''0'''11 (十进制 11)
   = 0'''0'''10 (十进制 2)
因为这条性质，通过查询最低位的值检查一个二进制数的[[奇偶性 (数学)|奇偶性]]变得容易。用以上的例子：
     0110 (十进制 6)
 AND 0001 (十进制 1)
   = 0000 (十进制 0)
因为6按位与1是0，6可以被2整除，所以6是偶数。

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

=== 数学等价物 ===
假设<math>x\geq y</math>，对于非负整数，按位运算可以被写成如下形式：
:<math>\begin{align}
   \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{align}</math>

=== 所有二元逻辑运算符的真值表 ===
两个{{En-link|二进制变量|Binary data}}有16种可能的[[真值函数]]；这定义了一个[[真值表]]。

这是两位 P 和 Q 的按位等效运算：
{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"
|-
! ''p'' !! ''q''
| rowspan=6 |
! [[矛盾|矛盾<sup>0</sup>]]
! [[逻辑或非]]<sup>1</sup>
! {{En-link|逆非蕴含|Converse nonimplication}}<sup>2</sup>
! '''[[逻辑非|非p]]'''<sup>3</sup>
! [[实质非蕴涵]]<sup>4</sup>
! '''[[逻辑非|非q]]'''<sup>5</sup>
! [[逻辑异或]]<sup>6</sup>
! [[逻辑与非]]<sup>7</sup>
| rowspan=6 |
! [[逻辑与]]<sup>8</sup>
! {{En-link|逻辑异或非|Logical biconditional}}<sup>9</sup>
! {{En-link|投射（集合论）|Projection (set theory)|q}}<sup>10</sup>
! [[实质条件]]<sup>11</sup>
! {{En-link|投射（集合论）|Projection (set theory)|p}}<sup>12</sup>
! [[逆命题]]<sup>13</sup>
! [[逻辑或]]<sup>14</sup>
! [[恆真式|恒真式]]<sup>15</sup>
|-
! 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
|-
! colspan="2" | 按位
等效
! <small>0</small>
! <small>NOT <br/>(p OR q)</small>
! <small>(NOT p) <br/>AND q</small>
! <small>NOT <br/>p</small>
! <small>p AND <br/>(NOT q)</small>
! <small>NOT <br/>q</small>
! <small>p XOR q</small>
! <small>NOT <br/>(p AND q)</small>
! <small>p AND q</small>
! <small>NOT <br/>(p XOR q)</small>
! <small>q</small>
! <small>(NOT p) <br/>OR q</small>
! <small>p</small>
! <small>p OR <br/>(NOT q)</small>
! <small>p OR q</small>
! <small>1</small>
|}
== 移位 ==
'''移位'''是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。在类C语言中，左移使用两个小于符号"<<"表示，右移使用两个大于符号">>"表示。

=== 位寻址 ===
[[File:Rotate left logically.svg|thumb|150px|算术左移|alt=thumb]]
[[File:Rotate right arithmetically.svg|thumb|算术右移|alt=thumb|150x150px]]

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

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

=== 算术移位 ===
{{Main2|[[算術移位]]}}在''算术移位''中，溢出两端的位都被丢弃。算术左移中，右侧补上0；算术右移中，左侧补上{{En-link|符号位|Sign bit}}（补码中的最高位），以保持原数的符号不变。

这个例子使用一个8位寄存器，解释为补码：
    00010111 (十进制 +23) LEFT-SHIFT
 =  0010111'''0''' (十进制 +46)
[[File:Rotate left logically.svg|thumb|150px|逻辑左移|alt=thumb]]
[[File:Rotate right logically.svg|alt=thumb|thumb|150x150px|逻辑右移]]
    10010111 (十进制 −105) RIGHT-SHIFT
 =  '''1'''1001011 (十进制 −53)
在第一种情况下，最左边的数字被移到寄存器的末尾，新的 0 被移到最右边的位置。 在第二种情况下，最右边的 1 被移出（可能进入了{{En-link|进位标志|Carry flag}}），一个新的 1 被复制到最左边的位置，保留了数字的符号。 多个移位有时会缩短为一个移位，减少了几位。 例如：
    00010111 (decimal +23) LEFT-SHIFT-BY-TWO
 =  010111'''00''' (decimal +92)
算术左移''n''位等价与乘以2<sup>''n''</sup> (前提值没有[[整数溢出]]）。一个[[补码]]的值算术右移''n'' 位等价与除以2<sup>''n''</sup> [[下取整]]。如果二进制数被视为[[一補數|一的补码]]，则相同的右移运算会导致除以2<sup>''n''</sup> 和[[数值修约|向零舍入]]。

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

但是，由于逻辑右移将值 0 位插入最高位，而不是复制符号位，因此它适用于无符号二进制数，而算术右移适用于有符号[[补码]]二进制数。
 -{}-   0001（十进制1）
 <<    3（左移3位）
  = 1000（十进制8）

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

=== 循环移位 ===
另一种移位是循环移位。
[[File:Rotate left.svg|alt=thumb|thumb|150x150px|循环左移或旋转]]
[[File:Rotate right.svg|alt=thumb|thumb|150x150px|循环右移或旋转]]

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

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

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

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

=== 在高级语言中 ===

==== 类C语言和Python ====
在[[C語言|類C語言]]和[[Python]]中，逻辑移位运算符是左移“<code><<</code>”和右移“<code>>></code>”。移位的位置数作为运算符的第二个参数给出。例如，<syntaxhighlight lang="c++">
x = y << 2;
</syntaxhighlight>将<code>x</code>赋值为<code>y</code>左移两位的结果，其等价于乘以四。

移位可能导致实现定义的行为或[[未定义行为]]，因此在使用它们时必须小心。 在 C 和 C++ 中，移位大于或等于字大小的位数是未定义的行为。<ref>{{Cite web |title=Arithmetic operators - cppreference.com |url=http://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators |website=en.cppreference.com |access-date=2016-07-06 |archive-date=2022-08-08 |archive-url=https://web.archive.org/web/20220808160141/https://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators |dead-url=no }}</ref>右移负值是实现定义的，但良好的编码实践不建议这样做；<ref>{{Cite web |title=INT13-C. Use bitwise operators only on unsigned operands |url=https://www.securecoding.cert.org/confluence/display/c/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands |website=CERT: Secure Coding Standards |publisher=Software Engineering Institute, Carnegie Mellon University |access-date=2015-09-07 |archive-date=2016-04-22 |archive-url=https://web.archive.org/web/20160422063607/https://www.securecoding.cert.org/confluence/display/c/INT13-C.%20Use%20bitwise%20operators%20only%20on%20unsigned%20operands |dead-url=no }}</ref>如果结果无法在结果类型中表示，则左移有符号值的结果是未定义的。<ref name=":0">[http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n843.htm JTC1/SC22/WG14 N843 "C programming language"] {{Wayback|url=http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n843.htm |date=20220803145528 }}, section 6.5.7</ref> 

在 C# 中，当第一个操作数是整形或长整形时，右移是算术移位。 如果第一个操作数是无符号整形或无符号长整形，则右移是逻辑移位。<ref>{{Cite web |title=Operator (C# Reference) |url=http://msdn.microsoft.com/en-us/library/xt18et0d%28v=vs.110%29.aspx |publisher=Microsoft |access-date=2013-07-14 |archive-date=2017-07-06 |archive-url=https://web.archive.org/web/20170706142910/https://msdn.microsoft.com/en-us/library/xt18et0d(v=vs.110).aspx |dead-url=no }}</ref>

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

==== JavaScript ====
[[JavaScript]]使用按位运算将两个或多个[[数字]]中的每一个求值为 1 或 0。<ref>[https://www.w3schools.com/js/js_bitwise.asp "JavaScript Bitwise"] {{Wayback|url=https://www.w3schools.com/js/js_bitwise.asp |date=20220812171324 }}. ''W3Schools.com''.</ref>

==== Pascal ====
在 Pascal 及其所有方言中（如 [[Object Pascal]] 和 {{En-link|Standard Pascal|GNU Pascal}}），逻辑左移运算符和右移运算符分别是“<code>shl</code>”和“<code>shr</code>”。 即使对于有符号整数， <code>shr</code> 的行为也类似于逻辑移位，并且不会复制符号位。 要移动的位置数作为第二个参数给出。 例如，下面将 y 左移两位的结果赋值给 x：<syntaxhighlight lang="pascal">
x := y shl 2;
</syntaxhighlight>

== 其他 ==

* [[汉明权重]]，在密码学中被使用
* {{En-link|计数前导零|Count leading zeros}}

== 应用 ==

[[Category:计算机算术]]
[[Category:程序架构]]
[[Category:布尔代数]]
[[Category:二进制算术]]
[[Category:运算符_(编程)]]
[[Category:需要计算机科学专家关注的页面]]
[[Category:带有伪代码示例的条目]]

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

尽管机器通常具有执行算术和逻辑运算的有效内置指令，但所有这些运算都可以通过以各种方式组合按位运算符和零测试来执行。<ref>{{Cite web |date=2014-02-15 |title=Synthesizing arithmetic operations using bit-shifting tricks |url=http://bisqwit.iki.fi/story/howto/bitmath/ |publisher=Bisqwit.iki.fi |access-date=2014-03-08 |archive-date=2014-03-08 |archive-url=https://web.archive.org/web/20140308061753/http://bisqwit.iki.fi/story/howto/bitmath/ |dead-url=no }}</ref>例如，这里是{{En-link|古埃及乘法|Ancient Egyptian multiplication}}的[[伪代码]]实现，展示了如何仅使用位移和加法将两个任意整数 <code>a</code> 和 <code>b</code>（<code>a</code> 大于 <code>b</code>）相乘：<syntaxhighlight lang="c">
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
</syntaxhighlight>另一个例子是加法的伪代码实现，展示了如何使用按位运算符和零测试计算两个整数 <code>a</code> 和 <code>b</code> 的和：<syntaxhighlight lang="c">
while a ≠ 0
    c ← b and a
    b ← b xor a
    left shift c by 1
    a ← c
return b
</syntaxhighlight>

== 参考 ==