不使用abs函数和if语句获取绝对值

Question

我在思考如何在不使用if语句或 abs()的情况下获取整数的绝对值。一开始我尝试使用左移位操作符(<<)，试图将负号移到范围之外，然后再右移回来，但很遗憾这种方法对我不起作用。请告诉我为什么它不起作用以及其他替代方法。

- shanwu

---

如果你知道正在处理的整数的大小，只需使用按位“与”来清除最高位。 - Marc B

这将适用于符号/大小表示法（这种表示法相当不寻常），但对于补码或（远远最常见的）二进制补码表示法则会出现严重失败。 - Jerry Coffin

@MarcB：对于二进制补码，情况比那稍微复杂一些。 - Oliver Charlesworth

这不是我的作业，而是我的编译器课程导师问的问题。我觉得这是一个有趣的问题，因为我以前从未这样做过。顺便说一句，解决这个问题不会提高我的课程成绩，但肯定会提高我的编码技能。^__^ - shanwu

@adembudak 这是关于无分支编程的问题，这是一种在代码的某些部分中不使用控制流（因此没有 if / else、三元运算符或循环）的编程技术。OP 想知道 如何 实现它，而不是一个执行此操作的函数的名称。 - Adam

Answer 1

来自位操作技巧：

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

- Hasturkun

---

v >> sizeof(int) * CHAR_BIT - 1 是一个位运算符，它将变量v向右移动(移除)了sizeof(int) * CHAR_BIT - 1个二进制位。其中sizeof(int)是int类型在当前平台上的字节数，CHAR_BIT表示每个字节中位的数量。这个操作通常用于获取v的最高位（即二进制表示中最左边的位），因为其余的位会被移出并丢失，而最高位则会被保留在v的最低位上。 - codey modey

我并非原作者，但这个问题与二进制补码表示有关。如果符号位被设置（因为它正在被右移，而且通常是算术右移，所以会发生符号扩展），那么掩码将等于全1。这相当于根据符号位将掩码设置为-1或0。 - Hasturkun

@codeymodey：CHAR_BIT是char类型中的位数，通常为8。它在limits.h中定义。对于32位整数，该表达式返回31。 - Hasturkun

有符号整数的右移实现是否由定义决定？基本上，我们为正数设置mask = 0x0，为负数设置mask=0xffffffff。"-((unsigned)num>>31)" 是正确的吗？还是说它更慢？ - Zxcv Mnb

@ZxcvMnb：是的，对有符号整数进行右移操作是实现定义的。正如我在之前的评论中提到的那样，这通常是算术右移（例如，GCC将其定义为这样）。我不知道你的变化是否更慢，但它可能需要更多的操作（即逻辑移位、取反而不是单个算术移位），无论如何，这两种变化都需要二进制补码表示法。链接页面有更多讨论，你可能会发现相关。 - Hasturkun

Answer 2

int abs(int v) 
{
  return v * ((v>0) - (v<0));
}

这段代码将v的值乘以-1或1，从而获得绝对值abs(v)。因此，括号内将是-1或1之一。

如果v为正数，则表达式(v>0)为真，并且其值为1，而(v<0)为假（false）（false的值为0）。因此，当v为正数时，((v>0) - (v<0)) = (1-0) = 1。整个表达式为：v * (1) == v。

如果v为负数，则表达式(v>0)为假，并且其值为0，而(v<0)为真（true）（true的值为1）。因此，对于负数v，((v>0) - (v<0)) = (0-1) = -1。整个表达式为：v * (-1) == -v。

当v == 0时，(v<0)和(v>0)都将计算为0，结果为：v * 0 == 0。

- perreal

---

只做 v * ((v>0) - (v<0)) 将是等效的且更易于阅读，不是吗？ - Jens Gustedt

Answer 3

无分支：

int abs (int n) {
    const int ret[2] = { n, -n };
    return ret [n<0];
}

_{注意 4.7 整数转换 / 4： [...] 如果源类型是 bool 类型，值 false 将被转换为零，值 true 将被转换为一。}

- Sebastian Mach

---

在C语言中，“branch-free”可能无法一次编译。有趣的是，“无分支”确实是目标代码的属性，而不是源代码的属性。 - Steve Jessop

@SteveJessop：但更严肃地说：可能使用任何半靠谱的编译器。然而，这也是代码结构中的无分支情况 :) - Sebastian Mach

好的，假设我说“编译后很可能不会出现这种情况”。我是对还是错，甚至有关系吗？;-) - Steve Jessop

不，我的“可能”是说“如果”的优雅简洁风格。我认为这个问题没有太多价值，我的答案更多是一种有意的咕哝演示 :P - Sebastian Mach

硬件如何实现从布尔值到整数的转换？这是否可以在没有条件分支的情况下完成？ - Kerrek SB

@KerrekSB：我猜不会有任何转换。编译器会识别操作数是0或1（另请参见4.7.整数转换），可能bool已经具有正确的索引大小，并且准备就绪。 - Sebastian Mach

Answer 4

我在C语言中尝试了这段代码，它可以运行。

int abs(int n){
   return n*((2*n+1)%2); 
}

希望这个答案能对您有所帮助。

- Quản Bá Hồng Nguyễn

---

这是最好的答案！！ - Raz Luvaton

针对大的 n 值会导致溢出。 - Markus

它运行非常良好，逻辑简单而强大。 - Kiran Chuahan

@KiranChuahan 不，2*n + 1会溢出，并且对于大数字它将无效。 - phuclv

为什么不直接使用 n * (n % 2); 呢？ - Narek Ghazaryan

@NarekGhazaryan 这将为偶数提供0。 - havakok

Answer 5

假设使用32位有符号整数（Java），可以编写以下代码：

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

没有乘法，也没有分支。

顺便说一下，return (x ^ (x >> 31)) - (x >> 31);同样可以工作，但它已经被专利保护了。是的！

注意：这段代码可能比条件语句（8位版本）慢10倍以上。这在硬件编程系统C等方面可能有用。

- flanglet

---

你怎么可能像那样申请专利呢？ - Jeremy Rodi

这个问题是针对 c 而不是 java 的。-1。 - Box Box Box Box

这段代码对于C和Java同样有效。将int替换为int32_t。 - RedOrav

这不能依赖于工作。对于负数的有符号整数右移，可以选择进行零填充或符号扩展。根据《C11标准草案》第6.5.7条第5款：“如果E1具有有符号类型并且具有负值，则结果值是实现定义的。” - Andrew Henle

Answer 6

我之前没有看到这个。对于二进制补码表示和32位整数

( n >> 31 | 1 ) * n

- MAG

---

非常棒的解决方案！这是一个更好的版本- ( n >> sizeof(int)*8-1 | 1 ) * n - Minhas Kamal

@MinhasKamal 不行。如果n是负数，并且在使用>>运算符时系统进行零填充，那么n >> 31位将会是0....0001，导致"绝对值"成为一个负数。根据C11 6.5.7p5规定（https://port70.net/~nsz/c/c11/n1570.html#6.5.7p5）："如果E1具有有符号类型并且具有负值，则结果值是实现定义的。" - Andrew Henle

@AndrewHenle 是的，这是基于算术移位实现的假设。 - undefined

Answer 7

请尝试以下操作：

int abs(int n) 
{
  return sqrt(n*n);
}

- Jeremy

---

sqrt函数很耗费资源，而且它接受的参数是double类型，所以你需要进行两次转换（int到double，再从double到int）。 - dousin

这实际上几乎让我找到了一个解决方案，其中我需要一个表达式，而函数不受支持（在ADO.Net DataColumn表达式中计算字段）。它也可以写成（n * n）^（1/2）。不幸的是，幂（^）也不受支持... - Louis Somers

除了速度慢之外，对于较大的 n 值，它会溢出，并且如果浮点类型不包含两倍于 int 的精度，则无法正确工作。 - phuclv

Answer 8

无分支或乘法：

int abs(int n) {
    int mask = n >> 31;
    return (mask & -n) | (~mask & n);
}

- TurplePurtle

Answer 9

以下是另一种方法，不使用abs()或任何逻辑/条件表达式：假设此处的int为32位整数。这个想法相当简单：(1-2*符号位)将把符号位=1/0转换为-1/1。

unsigned int abs_by_pure_math( int a ) {
   return (1 - (((a >> 31) & 0x1) << 1)) * a;
}

- dewang

Answer 10

如果您的语言允许将布尔型转换为整数（类似于C/C++）：

float absB(float n) {
    return n - n * 2.0f * ( n < 0.0f );
}

- Dani Barca Casafont