java - 如何使用位操作在java中获取数字的绝对值

Question

我想在java中实现一个获取数字绝对值的函数:如果是正数什么都不做，如果是负数，转换为正数。

我只想使用位操作而不使用数字比较器来做到这一点。

请帮忙

Answer 1

嗯，一个否定:

-n

与补码相同:

~n + 1

这里的问题是您只想在值小于 0 时取反。您可以通过使用逻辑移位来查看是否设置了 MSB 来找出答案:

n >>> 31

补码与全 1 的 XOR 相同，类似于(对于 4 位整数):

~1010 == 1010 ^ 1111

我们可以通过算术右移得到一个掩码:

n >> 31

绝对值表示:

• 如果 n < 0，取反(取补码并加 1)
• 否则，什么都不做

所以把它放在一起我们可以做以下事情:

static int abs(int n) {
    return (n ^ (n >> 31)) + (n >>> 31);
}

计算:

• 如果 n < 0，则将其与全 1 进行异或并加 1
• 否则，将其与全 0 进行异或并加 0

我不确定是否有一种不添加的简单方法。加法涉及任意数量的进位，即使是简单的增量也是如此。

例如 2 + 1 没有进位:

10 + 1 == 11

但是 47 + 1 有 4 个进位:

101111 + 1 == 110000

通过按位/位移进行加法和进位基本上只是一个循环展开并且毫无意义。

(编辑!)

开个玩笑，这里有一个增量和进位:

static int abs(int n) {
    int s = n >>> 31;
    n ^= n >> 31;

    int c;
    do {
        c = (n & s) << 1;
        n ^= s;
    } while((s = c) != 0);

    return n;
}

它的工作方式是翻转第一个位，然后一直翻转直到找到 0。所以接下来的工作就是展开循环。循环体可以用一个有点可笑的复合单行代码来表示。

static int abs(int n) {
    int s = n >>> 31;
    n ^= n >> 31;

    int c = (n & s) << 1;
    c = ((n ^= s) & (s = c)) << 1; // repeat this line 30 more times
    n ^= s;

    return n;
}

所以有一个 abs 只使用按位和位移位。

这些并不比 Math.abs 快。 Math.abs 只返回 n < 0 ? -n : n这是微不足道的。实际上，相比之下，循环展开完全糟透了。我猜只是出于好奇。这是我的基准:

Math.abs: 4.627323150634766nsshift/xor/add abs: 6.729459762573242nsloop abs: 12.028789520263672nsunrolled abs: 32.47122764587402nsbit hacks abs: 6.380939483642578ns

(bit hacks abs 是非专利的 shown here 与我的想法基本相同，只是有点难理解。)