8

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

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

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

4

2 回答 2

14

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

这可以通过

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

其中bit是位位置,bitval1 表示设置,0 表示复位。

更一般的情况如下:

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

实现了几个操作:

  • k1=0什么k2=0都不做
  • k1=0k2=1切换位
  • k1=1k2=0清除该位
  • k1=1k2=1设置位

更一般地与

value = (value & a) ^ x;

您可以决定同时更改几个value

  • aj=0, xj=0→ 将它们设置为 0
  • aj=0, xj=1→ 将它们设置为 1
  • aj=1, xj=0→ 保持原样
  • aj=1, xj=1→ 翻转它们

取决于预先计算的常数ax(ajxj是常数中第 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
于 2013-07-23T08:03:15.377 回答
12

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

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

所以设置一点:

i |= (1 << bit);

稍微重置一下:

i &= ~(1 << bit);

稍微切换一下:

i ^= (1 << bit);

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

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

于 2013-07-23T07:33:12.527 回答