设置或重置给定位而不进行分支

Question

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

在那之后，他们问我，做without branching。我不知道什么是分支。我寻找它，然后我来到这里，http://graphics.stanford.edu/~seander/bithacks.html

但是仍然不理解分支和非分支的概念。请解释一下Branching。

Answer 1

分支意味着cpu执行的指令包含条件跳转。非此即彼的选择。这可能意味着if、for-loop、while-loop、switch、?:或基于布尔值做出决策的东西。

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

因此，设置一下：

i |= (1 << bit);

重置一点：

i &= ~(1 << bit);

切换一下：

i ^= (1 << bit);

没有分支。实际上，我不明白如何让它变得如此复杂，以至于必须使用分支。

有人可能担心分支的原因是分支预测。See this question and answer for an excellent explanation of why it matters.

Answer 2

也许他们想让你展示如何编写一个没有分支的通用设置/重置代码段……

这可以通过以下命令来完成

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

其中，bit为位位置，bitval为1(表示设置)和0(表示复位)。

下面是一些更一般的东西：

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

它实现了几个操作：

• k1=0和k2=0执行nothing
• k1=0，k2=1切换bit
• k1=1，k2=0清除bit
• k1=1，k2=1设置

更一般地使用

value = (value & a) ^ x;

您可以通过以下方式决定同时更改value的多个位

• aj=0，0
• aj=0，xj=1
  • aj=0，them to 0
  • aj=0，xj=1
    • aj=0，them to 1
    • aj=1，xj=0→#en3#0
    • aj=0，xj=1xj=0 xj=1

    →→them to 0

  • aj=0，xj=1→to 0
  • aj=0，xj=0→→them 1
  • aj=1，xj=0→them untouched
  • aj=1，xj=1→→them
    • aj=0，

取决于预计算常数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