使用按位运算符和布尔逻辑的绝对值 abs(x)
Absolute value abs(x) using bitwise operators and Boolean logic
这是如何工作的？
想法是让 abs(x) 对整数使用按位运算符（假设 32 位字）：
y = x >> 31
(x + y) ^ y // This gives abs(x) (is ^ XOR)?
此方法依赖于许多特定于实现的行为：
- 假设
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
这不是便携式的。
假设 32 位字，如问题中所述：
对于负数 x，x >> 31 是在 C 和 C++ 标准中实现定义的。代码的作者期望二进制补码整数和算术右移，其中如果 x 的符号位为零，则 x >> 31 生成所有零位，如果符号位为一，则生成所有位。
因此，如果x为正数或零，则y为零，x + y为x，则(x + y) ^ y为x，也就是x.
的绝对值
如果x为负数，则y为全1，表示-1的补码。那么x + y就是x - 1。然后与所有的异或反转所有位。取反所有位相当于取二进制补码减一，二进制补码是二进制补码格式中整数取反的方法。换句话说，将 q 与所有值进行异或运算得到 -q - 1。所以 x - 1 与所有的异或产生 -(x - 1) - 1 = -x + 1 - 1 = -x，这是 x 的绝对值，除非 x 是最小值格式的可能值（−2,147,483,648 对于 32 位二进制补码），在这种情况下，绝对值 (2,147,483,648) 太大而无法表示，生成的位模式只是原始 x.
这不是便携式的，但我会解释为什么它仍然有效。
第一个操作利用了 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的原因是为了强制加法清零寄存器的特性。你看，如果它只是 x + ~(x)，那么你会得到一个全 1 的寄存器。通过向它加一，你得到一个级联进位，它产生一个零寄存器（寄存器的进位为 1）。
这种理解对于了解"why"您提供的算法（大部分）有效很重要。
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 的负数可以存储在相同数量的位中。
我使用这段代码，首先计算二进制补码（守卫只是确保编译时检查，模板是一个整数）
/**
* 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));
}
为什么我使用这种代码：
* 编译时检查
* 适用于所有整数大小
* 可从小型 µC 移植到现代内核
* 很明显，我们需要考虑二进制补码，所以你需要一个无符号的 return 值，例如对于 8 位 abs(-128)=128 不能用有符号整数表示
这是如何工作的？
想法是让 abs(x) 对整数使用按位运算符（假设 32 位字）：
y = x >> 31
(x + y) ^ y // This gives abs(x) (is ^ XOR)?
此方法依赖于许多特定于实现的行为：
- 假设
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
这不是便携式的。
假设 32 位字，如问题中所述：
对于负数 x，x >> 31 是在 C 和 C++ 标准中实现定义的。代码的作者期望二进制补码整数和算术右移，其中如果 x 的符号位为零，则 x >> 31 生成所有零位，如果符号位为一，则生成所有位。
因此，如果x为正数或零，则y为零，x + y为x，则(x + y) ^ y为x，也就是x.
如果x为负数，则y为全1，表示-1的补码。那么x + y就是x - 1。然后与所有的异或反转所有位。取反所有位相当于取二进制补码减一，二进制补码是二进制补码格式中整数取反的方法。换句话说，将 q 与所有值进行异或运算得到 -q - 1。所以 x - 1 与所有的异或产生 -(x - 1) - 1 = -x + 1 - 1 = -x，这是 x 的绝对值，除非 x 是最小值格式的可能值（−2,147,483,648 对于 32 位二进制补码），在这种情况下，绝对值 (2,147,483,648) 太大而无法表示，生成的位模式只是原始 x.
这不是便携式的，但我会解释为什么它仍然有效。
第一个操作利用了 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的原因是为了强制加法清零寄存器的特性。你看，如果它只是 x + ~(x)，那么你会得到一个全 1 的寄存器。通过向它加一，你得到一个级联进位，它产生一个零寄存器（寄存器的进位为 1）。
这种理解对于了解"why"您提供的算法（大部分）有效很重要。
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 的负数可以存储在相同数量的位中。
我使用这段代码，首先计算二进制补码（守卫只是确保编译时检查，模板是一个整数）
/**
* 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));
}
为什么我使用这种代码：
* 编译时检查
* 适用于所有整数大小
* 可从小型 µC 移植到现代内核
* 很明显，我们需要考虑二进制补码，所以你需要一个无符号的 return 值，例如对于 8 位 abs(-128)=128 不能用有符号整数表示