如何制作无网段代码？

问题描述

与此答案相关：

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

In the above answer, it's mentioned how you can avoid branch prediction fails by avoiding branches.

用户通过替换来证明这一点：

The user demonstrates this by replacing:

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

使用：

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

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

How are these two equivalent (for the specific data set, not strictly equivalent)?

在类似的情况下，我可以做些类似事情的一般方法是什么？总是使用>> 和〜？

What are some general ways I can do similar things in similar situations? Would it always be by using >> and ~?

推荐答案

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 if data [c]> = 128 ， 0 否则。

The trick here is that if data[c] >= 128, then data[c] - 128 is nonnegative, otherwise it is negative. The highest bit in an int, the sign bit, is 1 if and only if that number is negative. >> is a shift that extends the sign bit, so shifting right by 31 makes the whole result 0 if it used to be nonnegative, and all 1 bits (which represents -1) if it used to be negative. So t is 0 if data[c] >= 128, and -1 otherwise. ~t switches these possibilities, so ~t is -1 if data[c] >= 128, and 0 otherwise.

x& （-1）总是等于 x ， x& 0 始终等于 0 。所以 sum + = ~t&数据[c] 按 0 增加总和如果数据[ c]< 128 ，否则按 data [c] 。

x & (-1) is always equal to x, and x & 0 is always equal to 0. So sum += ~t & data[c] increases sum by 0 if data[c] < 128, and by data[c] otherwise.

其中许多技巧可以应用于其他地方。当且仅当一个值大于或等于另一个值且 -1时，此技巧当然可以通常应用于具有 0 的数字否则，您可以更多地使用它来获得< = ，< ，依此类推。像这样的小辫子是使数学运算无分支的常用方法，尽管它肯定不会总是用相同的操作构建; ^ （xor）和 | （或）有时也会发挥作用。

Many of these tricks can be applied elsewhere. This trick can certainly be generally applied to have a number be 0 if and only if one value is greater than or equal to another value, and -1 otherwise, and you can mess with it some more to get <=, <, and so on. Bit twiddling like this is a common approach to making mathematical operations branch-free, though it's certainly not always going to be built out of the same operations; ^ (xor) and | (or) also come into play sometimes.

这篇关于如何制作无网段代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！