c - 这个用位运算计算 3/4*x 的程序怎么解释？

Question

对于给定的int类型的值，使用最基本的位运算计算3/4*x(即没有while/for或其他 C 控制逻辑。还假设 sizeof(int) = 4 (Byte)。难点是向 0 截断并避免溢出。

我尝试过的:

假设将 x 表示为二进制形式:x = [b_31 b_30 ... b_2 b_1 b_0]
然后 3/4*x = x/2 + x/4 = ([b_31 ... b_1 0] + b_0) >> 1 + ([b_31 ... b_2 0 0] + b_1 b_0) >> 2
然后使用 x>>1 + x>>2 我们可以得到 [b_31 ... b_1 0]>>1 + [b_31 ... b_2 0 0]>>2 没有精度丢失或溢出问题，只留下 [b_0 0] + [b_1 b_0]>> 2 处理。但是我被困在这里，因为我不知道如何实现向零截断。

对比下面的示例程序，我发现使用了两个变量x_mask和bias。我猜它们是用来解决截断问题的，因为对于负数 bias 总是 11 而对于正数 00。谁能帮忙解释一下这里的逻辑？

int threefourths(int x) {
     int xl2 = x & 0x3;
     int xl1 = (x&1) << 1;
     int x_mask = x >> ((sizeof(int)<<3)-1);
     int bias = x_mask & 3;
     int incr = (xl2+xl1+bias) >> 2;
     int s2 = x >> 2;
     int s1 = x >> 1;
     return s1 + s2 + incr;
     }

Answer 1

我们要计算 0.75 * x，结果四舍五入为 0。因为 0.75 == 0.5 + 0.25，计算为 (x >> 1) + (x >> 2) 是一个很好的近似值，提供右移被映射到算术右移指令，ISO C 做的事情不保证。该标准规定:

The result of E1 >> E2 is E1 right-shifted E2 bit positions. [...] If E1 has a signed type and a negative value, the resulting value is implementation-defined.

近似值经常会低估期望的结果，因为 (1) 负整数除以算术右移轮到负无穷大，以及 (2) 与截断一次相比，截断这两个单独的项会导致低估，与引用计算一样。

因此我们知道可能需要应用校正，并且这种校正必须为零或正。因为除以 4，每个符号位设置有四种余数情况需要考虑，总共有八种情况。在发布的代码中，四种剩余情况被提取为 x & 3，与 x % 4 相同。我无法进一步了解代码的细节，但想展示一个更容易理解的替代方案。

八种可能情况的简单列举表明需要如下表所示的更正。对于属于八类中每一类的代表性值，通过从引用结果中减去近似值 (x >> 1) + (x >> 2) 来确定校正值，例如x 在 [0x7ffffffc, 0x80000003] 中。否定论点的修正大于肯定论点的修正，因为上面列举的两种低估效应结合在一起。

   s = sign bit, e.g. x<31>, x1 = bit x<1>, x0 = bit x<0>

   x%4 s x1 x0 | corr
   ------------+-----
    0  0  0  0 |  0
    1  0  0  1 |  0
    2  0  1  0 |  0
    3  0  1  1 |  1
    0  1  0  0 |  0
    1  1  0  1 |  1
    2  1  1  0 |  1
    3  1  1  1 |  2

很容易看出所需的修正等于 (x0 & x1) + (s & (x0 | x1))。我们可以以清晰度为代价稍微优化一下，如下面的实现所示:

int threefourths (int x) 
{
    int s2 = x >> 2; // ensure this maps to arithmetic right shift instruction
    int s1 = x >> 1; // ensure this maps to arithmetic right shift instruction
    unsigned int ux = (unsigned int)x;
    unsigned int s = ux >> (sizeof(ux) * CHAR_BIT - 1);
#if READABILITY
    unsigned int x0 = ux & 1;
    unsigned int x1 = s1 & 1;
    unsigned int corr = (x0 & x1) + (s & (x0 | x1));
#else // SPEED
    unsigned int corr = ((ux & s1) & 1) + (s & (ux | s1));
#endif // REDABILITY vs SPEED
    return (int)(s1 + s2 + corr);
}

int ref_threefourths (int x)
{
    return (int)((double)x * 0.75);
}