如何计算整数的绝对值

Question

如何在不使用if条件语句的情况下计算整数的绝对值？我猜我们需要使用一些位运算。有人可以帮忙吗？

- Pragyan

---

三元运算符是允许的吗？ - cnicutar

不，我猜你也不能使用那个。 - Pragyan

http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs - ltjax

你的动机是什么？性能？你是想通过消除分支来解决分支预测失败的问题吗？出于学术好奇心？作业？还是其他原因？ - Adrian McCarthy

对于ABS(INT_MIN)，正确的答案是什么？（为简单起见，使用8位）：理想情况下，ABS（-128）应该是128。但是有符号8位整数的最大值只有127！ - abelenky

Answer 1

与现有答案相同，但更详细的解释：

假设我们使用二进制补码（因为这是通常情况且您没有其他说明），并且假设为32位：

首先，我们进行一个算术右移31位。对于负数，这会将所有1位都向左移动，而对于正数则将所有0位向左移动（但请注意，在C或C++中实际的>>运算符的行为对于负数是有实现定义的，但通常也会执行算术移位，但让我们假设伪代码或实际的硬件指令，因为它听起来像是作业）：

mask = x >> 31;

因此，对于负数，我们得到的是111...111（-1），对于正数，我们得到的是000...000（0）。

现在，我们将其与x进行异或运算，对于mask=111...111（负数），得到NOT的行为，对于mask=000...000（正数），得到no-op（无操作）。

x = x XOR mask;

最后，我们要对掩码进行减法运算，对于负数结果为+1，对于正数结果为+0或无操作：

x = x - mask;

那么对于正数，我们执行0的异或操作和0的减法，从而得到相同的数字。而对于负数，我们有(NOT x) + 1，在使用二进制补码表示时，这恰好是-x。

- Christian Rau

---

感谢您的清晰解释，比被接受的答案好多了！请点赞支持。 - Skiptomylu

在C或C++中，这不会导致未定义的行为吗？如果x是INT_MIN，则XOR操作将使x == INT_MAX，并且将1添加到INT_MAX会导致溢出错误（对于有符号整数来说是未定义的行为）。 - Joshua Wise

@JoshuaWise 好的，我并没有假设特定的编程语言。在这种情况下，有符号右移将已经是实现定义的行为。 - Christian Rau

如果我来到这里搜索如何优化我在Hacker Rank上编写的解决方案，但实际上对答案中的任何内容都没有头绪，那我应该从哪里开始呢？为了更好地理解，我在HR解决方案中通过检查if值是否小于0并执行i = i + (i * -2)来实现i的绝对值。 - sixty4bit

如果您不了解此答案中提到的任何内容，恐怕您需要在其他地方寻找答案。您对绝对值的解决方案可能也有效，但这并不是问题所在。通常，要了解位运算的工作原理，一般的学习资源可能比试图浏览SO答案更好。 - Christian Rau

Answer 2

1. 将掩码设置为整数右移31位（假设整数存储为二进制补码32位值，并且右移运算符会进行符号扩展）。

mask = n>>31 

将掩码与数字进行异或运算

mask ^ n 

从步骤2的结果中减去掩码并返回结果。

(mask^n) - mask 

- Mady

---

请记住，并非所有语言都以相同的方式解释整数。有些语言支持正零和负零，其中abs（〜int）- abs（int）的结果为0，而您的解决方案要求：abs（abs（〜int）- abs（int））为1。 - dhein

@dhein 有哪种语言支持“-0”整数？我目前还没有听说过这样的语言。也许一些非常古老的硬件有这样的功能，因为工程师需要一点时间来决定使用哪种方案，但我也不知道有哪些硬件支持这个功能。顺便说一下，JavaScript 没有整数。它们在内部使用“double”，并在某些情况下将其处理为整数。 - Alexis Wilke

Answer 3

假设int为32位。

int my_abs(int x)
{
    int y = (x >> 31);
    return (x ^ y) - y;
}

- timrau

Answer 4

我们也可以这样执行上述操作：

return n*(((n>0)<<1)-1);

其中n是需要计算绝对值的数字。

- P.R.

Answer 5

在C语言中，你可以使用union来对双精度浮点数进行位操作。以下代码可以在C语言中运行，并且可用于整数、浮点数和双精度浮点数。

/**
* Calculates the absolute value of a double.
* @param x An 8-byte floating-point double
* @return A positive double
* @note Uses bit manipulation and does not care about NaNs
*/
double abs(double x)
{
    union{
        uint64_t bits;
        double dub;
    } b;

    b.dub = x;

    //Sets the sign bit to 0
    b.bits &= 0x7FFFFFFFFFFFFFFF;

    return b.dub;
}

请注意，这里假设double类型的数据占用8字节空间。

- Sheldon Juncker

Answer 6

在发现这个问题之前，我自己写了一个。

我的答案可能较慢，但仍然有效：

int abs_of_x = ((x*(x >> 31)) | ((~x + 1) * ((~x + 1) >> 31)));

- abelenky

Answer 7

如果不允许使用减号，您可以尝试以下方法：

int absVal(int x) {
  return ((x >> 31) + x) ^ (x >> 31);
}

- simibac

Answer 8

对于汇编语言来说，最高效的方法是将一个值初始化为0，减去这个整数，然后取最大值。

pxor mm1, mm1 ; set mm1 to all zeros
psubw mm1, mm0 ; make each mm1 word contain the negative of each mm0 word
pmaxswmm1, mm0 ; mm1 will contain only the positive (larger) values - the absolute value

- Antonin GAVREL

---

SSSE3（Core2及更高版本）直接具有pabsw。 - harold

是的，但问题被标记为“算法”，所以我假设作者不想要一个自动完成工作的库函数或指令 ;) - Antonin GAVREL

Answer 9

在C#中，你可以实现abs()函数而不使用任何局部变量：

public static long abs(long d) => (d + (d >>= 63)) ^ d;

public static int abs(int d) => (d + (d >>= 31)) ^ d;

注意：0x80000000（int.MinValue）和0x8000000000000000（long.MinValue）：

与本页上显示的所有其他按位/非分支方法一样，这会给出单个非数学结果abs(int.MinValue) == int.MinValue（对于long.MinValue也是如此）。这些表示结果值为负的唯一情况，即MSB的two's-complement结果为1 - 也是输入值未更改返回的唯一情况。我认为这个重要点在本页其他地方没有提到。

上面展示的代码取决于在计算左侧期间更新的d值用于右侧的xor的值。对于C#程序员来说，这似乎是显而易见的。他们习惯于看到像这样的代码，因为.NET正式包含了一个强大的内存模型，严格保证了正确的获取顺序。我提到这一点的原因是因为在C或C++中，人们可能需要更加谨慎。后者的内存模型相对宽松，这可能允许某些编译器优化发出无序获取。显然，在这种情况下，获取顺序的敏感性将代表一种正确性危险。

- Glenn Slayden

Answer 10

如果您不想依赖于符号扩展的实现来进行右位移，您可以修改计算掩码的方式：

mask = ~((n >> 31) & 1) + 1

然后按照之前的答案所演示的步骤继续进行：

(n ^ mask) - mask

- anfauglit