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

Question

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

c++cbit-manipulationlanguage-lawyerabsolute-value

53

这是怎么工作的？

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

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

- beta_me me_beta

11

@cMaster-ReinstateMonica，实际上我的意图是想学习它的工作原理。 - beta_me me_beta

13

如果你喜欢这种位操作的技巧，那么书籍《Hacker's Delight》（第二版）中有很多这样的位操作技巧。（“黑客”一词在旧时代有着积极的含义。） - Eljay

4

我很好奇，目前常用的ISA中，哪个ISA在非向量寄存器中具有整数绝对值指令？不是x86，也不是ARM。只有Power在SPE中有，xtensa也不算主流。除此之外，只有浮点数或向量寄存器。主要是因为编译器可以生成与OP代码完全对应的代码，所以CPU想象中需要的指令是不必要的。 - EOF

2

作为参考，我已经对(x^y)-y（类似版本）进行了分析，发现在x86-64上比std::abs(x)更快。 - geometrian

4

@EOF 实际上，我在考虑向量指令。但是即使是X86也有否定（像几乎所有的指令集一样）和条件移动。我的主要观点是：如果你知道比a >= 0 ? a : -a更快的方法，请告诉编译器的开发人员，他们会改变它的优化。 - cmaster - reinstate monica

显示剩余6条评论

4个回答

18

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

它假设x的位数为32位。但是，您可以通过x >> (sizeof(x) * CHAR_BIT - 1)来修复这个问题。
它假设机器使用二进制补码表示法。
右移操作符将符号位从左向右复制。

使用3位进行示例：

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

101 + 111 = 100 -> x + y

100 XOR 111 -> 011 -> 3

这不是可携带的。

- Ayxan Haqverdili

2

我不是其中之一，但这并不能回答 OP 的问题。只有评论可以。 - solid.py

不是我的DV，我也没有阅读C++20标准，但在C语言（当前也被标记），负有符号值的右移是实现定义的，因此这种方法还存在其他问题。 - Andrew Henle

3

在这个问题中，“xor”运算是针对“y”（而不是“x”）进行的。 - BiagioF

3

代码并没有假定int为32位，因为问题中根本没有提到int。代码明确表示它正在处理的单词，无论它们是什么类型，都是32位的。 - Eric Postpischil

1

@EricPostpischil感谢您的反馈。这个改述是否更好？ - Ayxan Haqverdili

显示剩余5条评论

12

这不是可移植的，但我会解释为什么它能工作。

第一个操作利用了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进制补码编码数字的原因是，任何负数加上它的正数会得到0这一特性。现在，要创建2进制补码数的负数，需要执行以下步骤：

1. 对输入数取反（按位非）。 2. 加1。

之所以要加1，是为了强制实现加法将寄存器清零的特性。如果只是x + ~(x)，那么会得到一个全1的寄存器。通过加1，可以得到一个级联进位，从而产生一个全0的寄存器（带有寄存器的进位输出为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 都大。

- Edwin Buck

最后一段：x = 0xFFFFFFFF 是 -1。我认为你指的是 x = 0x80000000，这是二进制补码中最小的负数特殊情况。你可以通过将结果处理为无符号值来解决这个问题。(并且要小心编写代码，避免 C 语言中有符号溢出 UB 的可能性，例如通过使用无符号减法避免从 0x7FFFFFFF 溢出到 0x80000000) - Peter Cordes

你的符号表示很奇怪；你似乎使用 ! 来进行位求反运算（按位取反）。但这是一个 C 语言问题；在 C 中，该运算符应该是 ~（波浪号）。在 C 中，! 表示逻辑非，只能产生 0 或 1。 - Peter Cordes

@PeterCordes 我错过了第一个评论，我也会修复它。感谢您的仔细阅读。 - Edwin Buck

我在问题得到解决之前暂时不进行点赞。现在看起来很好。有一些关于进位传递如何翻转位以将-1变为0的有趣讨论。 - Peter Cordes

4

我使用这段代码，首先计算二进制补码（guard 仅通过编译时检查确保模板为整数）。

/**
 * Zweierkomplement - Two's Complement
 */
template<typename T> constexpr auto ZQ(T const& _x) noexcept ->T{
  Compile::Guards::IsInteger<T>();
  return ((~(_x))+1);
}

其次，使用这个值计算整数 abs() 函数。

/**
 * if number is negative, get the same number with positiv sign
 */
template<typename T> auto INTABS(T const _x) -> typename std::make_unsigned<T>::type{
  Compile::Guards::IsInteger<T>();
  return static_cast<typename std::make_unsigned<T>::type>((_x<0)?(ZQ<T>(_x)):(_x));
}

为什么要使用这种代码：
* 编译时检查
* 适用于所有整数大小
* 从小型微控制器到现代核心的可移植性
* 明确需要考虑二进制补码，因此需要一个无符号的返回值，例如对于8位的 abs(-128)=128 无法用有符号整数表达。

- schnedan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric Postpischil · Accepted Answer

假设32位字长，根据问题所述：

对于负数x，在C和C ++标准中，x >> 31是实现定义的。代码作者期望使用二进制补码整数和算术右移，在这种情况下，如果x的符号位为零，则x >> 31产生所有零位，如果符号位为1，则产生所有1位。

因此，如果x是正数或零，则y为零，x + y即为x，所以(x + y) ^ y等于x，即x的绝对值。

如果x是负数，y的所有位都是1，代表二进制补码的-1。那么x+y等于x-1。然后与全1异或将反转所有位。反转所有位相当于取二进制补码再减1，而二进制补码是用于在二进制补码格式中表示负整数的方法。换句话说，与全1异或的结果为-q-1。因此，x-1与全1异或的结果为-(x-1)-1=-x+1-1=-x，这是x的绝对值（除非x是该格式的最小可能值（32位二进制补码的-2,147,483,648），此时绝对值（2,147,483,648）太大无法表示，结果的位模式就是原始的x）。