“分支”在设置/重置位方面意味着什么？

Question

在一次采访中，他们问我，你如何设置或重置一点？这是一个非常简单的问题，我回答了。

之后他们问我如何在不分支的情况下做到这一点。我不知道什么是分支。

我搜索并找到了 Sean Eron Anderson 的 Bit Twiddling Hacks，但我仍然不明白分支和非分支的概念。

请解释一下“分支”。

Answer 1

也许他们希望您展示如何编写没有分支的通用设置/重置片段。

这可以通过

来完成

value = (value & ~(1 << bit)) | (bitval << bit);

其中

bit

是位位置，

bitval

为 1 表示设置，0 表示重置。

更一般的事情如下：

value = (value & ~(k1 << bit)) ^ (k2 << bit);

实现了多种操作：

• k1=0

  和

  k2=0

  什么都不做

• k1=0

  和

  k2=1

  切换位

• k1=1

  和

  k2=0

  清除该位

• k1=1

  和

  k2=1

  设置位

更普遍的是

value = (value & a) ^ x;

您可以通过

决定同时更改

value

的多个位

• aj=0

  、

  xj=0

  → 将它们设置为 0

• aj=0

  、

  xj=1

  → 将它们设置为 1

• aj=1

  、

  xj=0

  →保持原样

• aj=1

  、

  xj=1

  → 翻转它们

取决于预先计算的常量

a

和

x

（

aj

和

xj

是常量中第j位的值）。

例如

value = (value & 0x0F) ^ 0x3C;

只需一次操作即可

- leave untouched bit 0 and 1
- flip bits 2 and 3
- set to 1 bits 4 and 5
- set to 0 all other bits

Answer 2

分支是指CPU执行的指令包含条件跳转。一个非此即彼的选择。这可能意味着

if

、

for

循环、

while

循环、

switch

、

?:

或基于布尔值做出决定的东西。

人们经常忘记的一类分支也是短路布尔运算符，以及可能（但不一定在所有 CPU 上）评估为真值的东西，因此

int foo; ...; foo = !foo;

将是某些 CPU 上的分支，但不是所有（不是所有 CPU）上的分支在 x86 上）。

所以要设置一点：

i |= (1 << bit);

稍微重置一下：

i &= ~(1 << bit);

稍微切换一下：

i ^= (1 << bit);

没有分支机构。我实际上不知道如何使这个变得如此复杂以至于必须使用分支。

有人可能想要担心分支的原因是分支预测。 请参阅此问题和答案，以获得其重要性的精彩解释。