如何制作无分支代码？

Question

与此答案相关的信息：http://codingdict.com/questions/122892

在上面的答案中，提到了如何通过避免分支来避免分支预测失败。

用户通过替换以下内容进行演示：

if (data[c] >= 128)
{
    sum += data[c];
}

带有：

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这两个等效项如何（对于特定数据集，不是严格等效的）？

在类似情况下我可以做哪些一般的事情？是否总是使用>>和~？

Answer 1

int t = (data[c] - 128) >> 31;

这里的技巧是，如果data[c] >= 128，data[c] - 128则为非负数，否则为负数。int当且仅当该数字为负数时，符号位中的最高位为1。
>>是对符号位进行扩展的移位，因此如果过去一直为非负值，则将结果右移31将使 整个
结果为0，如果曾经为负，则将全部为1位（代表-1）。所以t是0如果data[c] >= 128，和-1其他。
~t切换这些可能性，所以~t是-1如果data[c] >= 128和0其它。

x & (-1)总是等于x并且x & 0总是等于0。因此，通过if sum += ~t & data[c]增加，否则增加。sum``0``data[c] < 128``data[c]

这些技巧很多都可以应用于其他地方。0当且仅当一个值大于或等于另一个值时，通常可以应用此技巧以使数字为be
，-1否则，并且您可以将其弄乱一些以获得<=，<等等。像这样的位旋转是使数学运算无分支的一种常用方法，尽管它不一定总是由相同的运算构建而成。^（xor）和|（or）有时也会起作用。