使用按位运算符和布尔逻辑的绝对值 abs(x)

Question

这是如何运作的？

这个想法是abs(x)对整数使用按位运算符（假设为 32 位字）：

y = x >> 31
(x + y) ^ y // This gives abs(x) (is ^ XOR)?

Answer 1

假设 32 位字，如问题所述：

对于 negative x，x >> 31在 C 和 C++ 标准中是实现定义的。代码的作者期望二进制补码整数和算术右移，x >> 31如果符号位为零，则生成全零位，如果符号位为一，x则生成全一位。

因此，如果x是正数或零，y则为零，并且x + y是x，因此(x + y) ^ y是x，这是 的绝对值x。

如果x为负，y则为全1，表示补码中的?1。然后x + y是x - 1。然后与所有 1 进行异或将所有位反转。将所有位取反就相当于取二的补码减一，二的补码是用来取反二进制补码格式的整数的方法。换句话说，q与所有的异或给出-q - 1. 所以x - 1全部为一异或产生-(x - 1) - 1= -x + 1 - 1= -x，这是的绝对值x除时x为格式的最小可能值（？2147483648用于32位2的补码），在这种情况下，绝对值（2147483648）是太大而不能表示，并且生成的位模式只是原始的x.

Answer 2

这种方法依赖于许多特定于实现的行为：

1. 它假设x是 32 位宽。虽然，你可以解决这个问题x >> (sizeof(x) * CHAR_BIT - 1)
2. 它假设机器使用二进制补码表示。
3. 右移运算符从左到右复制符号位。

3 位示例：

101 -> x = -3
111 -> x >> 2

101 + 111 = 100 -> x + y

100 XOR 111 -> 011 -> 3

这不是便携式的。

Answer 3

这不是便携式的，但我会解释为什么它仍然有效。

第一个操作利用了 2 的负数补码的特性，即第一位如果为负则为 1，如果为正则为 0。这是因为数字范围从

下面的示例针对 8 位，但可以外推到任意数量的位。在您的情况下，它是 32 位（但 8 位更容易显示范围）

10000000 (smallest negative number)
10000001 (next to smallest)
...
11111111 (negative one)
00000000 (zero)
00000001 (one)
...
01111110 (next to largest)
01111111 (largest)

使用数字的 2 的补码编码的原因来自这样的特性：将任何负数添加到它的正数会产生零。

现在，要创建 2 的补数的负数，您需要

1. 取输入数字的倒数（按位非）。
2. 添加一个。

将 1 添加到其中的原因是强制加法功能将寄存器清零。你看，如果它只是 x + ~(x)，那么你会得到一个全 1 的寄存器。通过给它加一个，你会得到一个级联进位，它产生一个零寄存器（寄存器的进位输出为 1）。

这种理解对于了解您提供的算法（大部分）有效的“原因”很重要。

y = x >> 31   // this line acts like an "if" statement.
              // Depending on if y is 32 signed or unsigned, when x is negative, 
              // it will fill y with 0xFFFFFFFF or 1.  The rest of the 
              // algorithm doesn't, care because it accommodates both inputs.
              // when x is positive, the result is zero.

我们将探索（首先x为正）

(x + y) ^ y   // for positive x, first we substitute the y = 0
(x + 0) ^ 0   // reduce the addition
(x) ^ 0       // remove the parenthesis
x ^ 0         // which, by definition of xor, can only yield x
x

现在让我们探索一下（x 为负数，y 为 0xFFFFFFFF（y 有符号））

(x + y) ^ y   // first substitute the Y
(x + 0xFFFFFFFF) ^ 0xFFFFFFFF // note that 0xFFFFF is the same as 2's complement -1
(x - 1) ^ 0xFFFFFFFF // add in a new variable Z to hold the result
(x - 1) ^ 0xFFFFFFFF = Z  // take the ^ 0xFFFFFFFF of both sides
(x - 1) ^ 0xFFFFFFFF ^ 0xFFFFFFFF = Z ^ 0xFFFFFFFF // reduce the left side
(x - 1) = z ^ 0xFFFFFFFF // note that not is equivalent to ^ 0xFFFFFFFF
(x - 1) = ~(z) // add one to both sides
x - 1 + 1 = ~(z) + 1 //  reduce
x = ~(z) + 1  // by definition z is negative x (for 2's complement numbers)

现在让我们探索一下（x 是负数，y 是 0x01（y 是无符号的））

(x + y) ^ y   // first substitute the Y
(x + 1) ^ 0x00000001 // note that x is a 2's complement negative, but is
                     // being treated as unsigned, so to make the unsigned
                     // context of x tracable, I'll add a -(x) around the X
(-(x) + 1) ^ 0x00000001 // which simplifies to
(-(x - 1)) ^ 0x00000001 // negative of a negative is positive
(-(x - 1)) ^ -(-(0x00000001)) // substituting 1 for bits of -1
(-(x - 1)) ^ -(0xFFFFFFFF) // pulling out the negative sign
-((x-1) ^ 0xFFFFFFFF) // recalling that while we added signs and negations to
                      // make the math sensible, there's actually no place to
                      // store them in an unsigned storage system, so dropping
                      // them is acceptable
x-1 ^ 0XFFFFFFFF = Z // introducing a new variable Z, take the ^ 0xFFFFFFF of both sides
x-1 ^ 0xFFFFFFFF ^ 0xFFFFFFFF = Z ^ 0xFFFFFFFF // reduce the left side
x-1 = z ^ 0xFFFFFFFF // note that not is equivalent to ^ 0xFFFFFFFF
x-1 = ~(z) // add one to both sides
x - 1 + 1 = ~(z) + 1 //  reduce
x = ~(z) + 1  // by definition z is negative x (for 2's complement numbers, even though we used only non-2's complement types)

请注意，虽然上述证明对于一般解释是可以通过的，但实际情况是这些证明不包括重要的边缘情况，例如 x = 0x80000000 ，它表示绝对值大于任何正 X 的负数，它可以存储在相同的位数。