c - 设置或重置给定位而不分支

Question

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

之后他们问我，做那个without branching。我不知道什么是分支。我搜索并来到这里 http://graphics.stanford.edu/~seander/bithacks.html

但仍然没有得到分支和非分支的概念。请解释Branching。

Answer 1

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

这可以通过

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

其中bit是位位置，bitval1 表示设置，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-loop，while-loop switch，?:或基于布尔值做出决定的东西。

人们经常忘记的一类分支也是短路布尔运算符和可能（但不一定在所有 CPU 上）评估为真值的东西，因此int foo; ...; foo = !foo;在某些 CPU 上是一个分支，但不是全部（不是在 x86 上）。

所以设置一点：

i |= (1 << bit);

稍微重置一下：

i &= ~(1 << bit);

稍微切换一下：

i ^= (1 << bit);

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

有人可能要担心分支的原因是分支预测。请参阅此问题和答案，以很好地解释为什么它很重要。