时间戳

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

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

问题描述

我正在寻找一种简洁的方法（很可能是“按位快捷方式”）来计算表达式的有符号值(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();
}

请假设我手头没有更大的类型。

我很乐意阅读有关如何使其更简单/更短/更整洁的任何想法。

标签： bit-manipulationunsignedsignedtwos-complementinteger-division

解决方案

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

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

首先得到一个所有位都设置为 iff 的掩码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);

推荐阅读