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

Question

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

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

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

Answer 1

分支意味着cpu执行的指令包含条件跳转.一个或两个选择.这可能意味着a if,for-loop,while-loop switch,?:或基于布尔值做出决定的事情.

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

所以设置一下:

i |= (1 << bit);

重置一下:

i &= ~(1 << bit);

切换一下:

i ^= (1 << bit);

没有分支.我实际上不知道如何使这个如此复杂,必须使用分支.

有人可能想要担心分支的原因是分支预测.请参阅此问题和答案,以获得有关其重要性的出色解释.

Answer 2

可能是他们想让你展示如何编写一个没有分支的通用设置/重置片段...

这可以用

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