给定无符号操作数，计算 `(x - y) / z` 有符号结果的按位快捷方式

Question

我正在寻找一种简洁的方法（很可能是“按位快捷方式”）来计算表达式 (x - y) / z 的有符号值，给定无符号操作数 x、y 和 z.

这是一个“有点真实有点伪”的代码，说明我目前正在做什么（请不要介意实际语法是“100% 完美的 C 或 C++”）：

int64 func(uint64 x, uint64 y, uint64 z)
{
    if (x >= y) {
        uint64 result = (x - y) / z;
        if (int64(result) >= 0)
            return int64(result);
    }
    else {
        uint64 result = (y - x) / z;
        if (int64(result) >= 0)
            return -int64(result);
    }
    throwSomeError();
}

请假设我手头没有更大的字体。

我很乐意阅读有关如何制作此内容的任何想法simpler/shorter/neater。

Answer 1

有一个捷径，通过使用按位技巧进行两次条件否定（一次求绝对差，然后再次恢复符号）。

我想我会使用一些类似的不完美的 C-ish 语法来匹配问题。

首先得到一个所有位都设置的掩码当且仅当x < y:

uint64 m = -uint64(x < y);

(x - y)和-(y - x)实际上是一样的，即使在无符号算术中也是如此，条件取反可以通过使用补码的定义来完成：-a = ~(a - 1) = (a + (-1) ^ -1)。 (a + 0) ^ 0当然又等于a，所以当m为-1时，(a + m) ^ m = -a而当m为零时，则为a .所以这是一个条件否定。

uint64 absdiff = (x - y + m) ^ m;

然后照常除法，再做一次条件取反恢复符号：

return int64((absdiff / z + m) ^ m);

给定无符号操作数，计算 `(x - y) / z` 有符号结果的按位快捷方式

A bitwise shortcut for calculating the signed result of `(x - y) / z`, given unsigned operands

bit-manipulation

unsigned

signed

twos-complement

integer-division