如何使用位操作获取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.627323150634766ns
shift/xor/add abs: 6.729459762573242ns
loop abs: 12.028789520263672ns
unrolled abs: 32.47122764587402ns
bit hacks abs: 6.380939483642578ns

(这里显示的是非专利的,这是一个非专利的,与我的基本相同的想法,除了有点难以理解.)