“算术右移”操作类似于正常(逻辑)右移,除了最高有效位 (即移入) 位填充有符号位而不是0。不幸的是,在C中(在C20之前,也在C中),对有符号整数执行右移的结果是[编译器/平台]实现定义的。有没有一种方法可以执行“算术右移”,无论实现细节如何,都能保证提供正确的结果?理想情况下,代码足够简单,可以内联,并且不包含任何条件或分支。
dffbzjpn1#
只需使用>>操作符,但要使用更宽的整数:
#include "stdio.h" #include <stdint.h> int32_t sar(int32_t val, unsigned sh) { return (int32_t)((int64_t)val >> sh); } volatile int32_t value=-128; volatile unsigned shift=1; int main(void) { volatile int32_t result = sar (value, shift); printf("sar(%d, %u) = %d\n", value, shift, result); return 0; }
我的gcc内联了sar(),但没有声明它内联,并将main()编译为:
sar()
main()
main: .LFB31: .cfi_startproc endbr64 sub rsp, 24 .cfi_def_cfa_offset 32 mov ecx, DWORD PTR shift[rip] movsx rax, DWORD PTR value[rip] lea rsi, .LC0[rip] mov edi, 1 sar rax, cl ;<--------Shift Arithmetically Right mov DWORD PTR 12[rsp], eax mov r8d, DWORD PTR 12[rsp] xor eax, eax mov ecx, DWORD PTR shift[rip] mov edx, DWORD PTR value[rip] call __printf_chk@PLT xor eax, eax
rkue9o1l2#
下面是一个C++内联函数,它对一个有符号的32位整数执行“算术右移”,而不管实现细节如何,也没有条件或分支。如果需要,它可以很容易地适应C。
#include <cstdint> inline int32_t sar(int32_t val, unsigned int sh) { uint32_t uval = static_cast<uint32_t>(val); uint32_t result = (uval >> sh) | -((uval & 0x80000000) >> sh); return static_cast<int32_t>(result); }
说明:函数名sar代表“shift arithmetic right”(算术右移),这让人联想到常见的汇编助记符。该函数接受一个有符号的32位整数val作为要移位的值,接受一个无符号整数sh作为要右移的位数。* * 注意:在某些平台上,右移等于或大于被移位值的位宽的位数可能会导致未定义的行为!您可以限制sh(在本例中为31)以避免这种可能性。**由于对有符号整数右移的结果是实现定义的,因此我们所有的操作都将使用无符号数完成。我们首先将输入值转换为无符号整数uval。接下来,我们执行正确的移位。由于这是无符号移位,因此最高有效 (即移入) 位填充0。然而,对于正确的算术右移,我们希望它们用 * 符号位 * 填充,这是原始值的最高有效位。表达式-((uval & 0x80000000) >> sh)提供了我们需要的高阶符号位串。首先,我们使用带有掩码的按位AND(&)来提取最高有效位,即符号位。然后,我们将此位移到正确的sh位置。接下来,我们对结果求反,对无符号整数执行2的补码运算。这给了我们一个所有高阶位都被设置为等于[移位]符号位的数!最后,我们执行按位OR(|)将这些符号位与移位的uval组合,用符号位填充高阶位。在C++11或更高版本中,我们可以使用以下模板来处理任何有符号整数类型:
sar
val
sh
uval
-((uval & 0x80000000) >> sh)
&
|
#include <type_traits> template<typename T> typename std::enable_if<std::is_signed<T>::value && std::is_integral<T>::value, T>::type sar(T val, unsigned int sh) { using UnsignedT = typename std::make_unsigned<T>::type; UnsignedT uval = static_cast<UnsignedT>(val); UnsignedT high_bit = static_cast<UnsignedT>(-1); high_bit = high_bit ^ (high_bit >> 1); UnsignedT result = (uval >> sh) | -((uval & high_bit) >> sh); return static_cast<T>(result); }
从模板类型T计算high_bit的解释留给读者作为练习。在C20和更高版本中,右位移位运算符>>被保证为 * 算术右移 *。对于早期的语言版本,当然有各种各样的库和其他解决方案来解决这个问题,但这个基于纯C代码的答案是迂腐的。
T
high_bit
>>
oewdyzsn3#
直接对有符号整数使用>>即可。
主要的编译器都记录了它执行算术移位:
而且,正如你所说,C++20保证了>>的符号扩展。我相当肯定这只是标准化了编译器正在做的事情。为了确定,添加一个测试:
static_assert(-4 >> 1 == -2, ">> doesn't do sign extension");
gtlvzcf84#
扩展一下其他人的答案,这里是c版本的函数,它计算32位和64位有符号整数的“shift-arithmetic-right”,没有分支。然而,最终的结果是有问题的。
int32_t sar32(int32_t val, uint8_t sh) { sh &= 0x1f; uint32_t uval = (uint32_t)val; uint32_t result = (uval >> sh) | -((uval & 0x80000000) >> sh); return (int32_t)result; } int32_t sar32b(int32_t val, uint8_t sh) { sh &= 0x1f; uint64_t uval = val; return (int32_t)(uval >> sh); } int64_t sar64(int64_t val, uint8_t sh) { sh &= 0x3f; uint64_t uval = (uint64_t)val; uint64_t result = (uval >> sh) | -((uval & 0x8000000000000000UL) >> sh); return (int64_t)result; }
这些函数会对sh的输入进行清理,以使移位安全,但是如果输入了允许范围之外的值,它们会以一种环绕的方式来执行此操作。为了避免 Package ,就像
sh = (sh >= 0x1f ? 0x1f : sh & 0x1f);
但是这引入了分支。避免这种情况的一种方法是引入另一个变量
uint8_t sh2 = ((sh >= 0x1f)*0x1f) | (sh & 0x1f);
然后跟着它移动我认为值得一提的是,虽然下面的函数使用gcc(确保符号扩展)编译,并且即使使用-Wall -fsanitize=undefined标志也不会发出警告,但在需要严格遵守c标准的情况下不应该使用它,因为右移负整数值是c中实现定义的行为。
int32_t sar(int32_t val, uint8_t sh) { return val >> (sh & 0x1f); // DO NOT USE IF val < 0!!! }
对于32位和64位的非分支函数,它们使用基于联合的类型双关,这是一种(据称)在“现代”c中没有以任何方式定义的行为,并且不包含移位量,如下所示。这种方法可能不会延续到c++。
int32_t sar32(int32_t val, uint8_t sh) { uint8_t sh2 = ((sh >= 0x1f)*0x1f) | (sh & 0x1f); union { int64_t i; uint64_t u; } input = {0}; input.i = val; input.u >>= sh2; return (int32_t)input.i; } int64_t sar64(int64_t val, uint8_t sh) { uint8_t sh2 = ((sh >= 0x3f)*0x3f) | (sh & 0x3f); union { int64_t i; uint64_t u; } input = {0}; input.i = val; input.u = (input.u >> sh2) | -((input.u & 0x8000000000000000UL) >> sh2); return input.i; }
一种比较费力的方法(可能更好地转换为其他语言,如c++)是使用memcpy。
int32_t sar32(int32_t val, uint8_t sh) { uint8_t sh2 = ((sh >= 0x1f)*0x1f) | (sh & 0x1f); int32_t result; uint32_t uval32, uval32mask; memcpy(&uval32, &val, 4); uval32mask = -(uval32 >> 31); uval32 = (uval32 >> sh2) | (uval32mask << (31 - sh2)); memcpy(&result, &uval32, 4); return result; } int64_t sar64(int64_t val, uint8_t sh) { uint8_t sh2 = ((sh >= 0x3f)*0x3f) | (sh & 0x3f); int64_t result; uint64_t uval64, uval64mask; memcpy(&uval64, &val, 8); uval64mask = -(uval64 >> 63); uval64 = (uval64 >> sh2) | (uval64mask << (63 - sh2)); memcpy(&result, &uval64, 8); return result; }
4条答案
按热度按时间dffbzjpn1#
只需使用>>操作符,但要使用更宽的整数:
我的gcc内联了
sar()
,但没有声明它内联,并将main()
编译为:rkue9o1l2#
下面是一个C++内联函数,它对一个有符号的32位整数执行“算术右移”,而不管实现细节如何,也没有条件或分支。如果需要,它可以很容易地适应C。
说明:
函数名
sar
代表“shift arithmetic right”(算术右移),这让人联想到常见的汇编助记符。该函数接受一个有符号的32位整数val
作为要移位的值,接受一个无符号整数sh
作为要右移的位数。* * 注意:在某些平台上,右移等于或大于被移位值的位宽的位数可能会导致未定义的行为!您可以限制sh
(在本例中为31)以避免这种可能性。**由于对有符号整数右移的结果是实现定义的,因此我们所有的操作都将使用无符号数完成。我们首先将输入值转换为无符号整数
uval
。接下来,我们执行正确的移位。由于这是无符号移位,因此最高有效 (即移入) 位填充0。然而,对于正确的算术右移,我们希望它们用 * 符号位 * 填充,这是原始值的最高有效位。
表达式
-((uval & 0x80000000) >> sh)
提供了我们需要的高阶符号位串。首先,我们使用带有掩码的按位AND(&
)来提取最高有效位,即符号位。然后,我们将此位移到正确的sh
位置。接下来,我们对结果求反,对无符号整数执行2的补码运算。这给了我们一个所有高阶位都被设置为等于[移位]符号位的数!最后,我们执行按位OR(|
)将这些符号位与移位的uval
组合,用符号位填充高阶位。在C++11或更高版本中,我们可以使用以下模板来处理任何有符号整数类型:
从模板类型
T
计算high_bit
的解释留给读者作为练习。在C20和更高版本中,右位移位运算符
>>
被保证为 * 算术右移 *。对于早期的语言版本,当然有各种各样的库和其他解决方案来解决这个问题,但这个基于纯C代码的答案是迂腐的。oewdyzsn3#
直接对有符号整数使用
>>
即可。主要的编译器都记录了它执行算术移位:
而且,正如你所说,C++20保证了
>>
的符号扩展。我相当肯定这只是标准化了编译器正在做的事情。为了确定,添加一个测试:
gtlvzcf84#
扩展一下其他人的答案,这里是c版本的函数,它计算32位和64位有符号整数的“shift-arithmetic-right”,没有分支。然而,最终的结果是有问题的。
这些函数会对sh的输入进行清理,以使移位安全,但是如果输入了允许范围之外的值,它们会以一种环绕的方式来执行此操作。为了避免 Package ,就像
但是这引入了分支。避免这种情况的一种方法是引入另一个变量
然后跟着它移动
我认为值得一提的是,虽然下面的函数使用gcc(确保符号扩展)编译,并且即使使用-Wall -fsanitize=undefined标志也不会发出警告,但在需要严格遵守c标准的情况下不应该使用它,因为右移负整数值是c中实现定义的行为。
对于32位和64位的非分支函数,它们使用基于联合的类型双关,这是一种(据称)在“现代”c中没有以任何方式定义的行为,并且不包含移位量,如下所示。这种方法可能不会延续到c++。
一种比较费力的方法(可能更好地转换为其他语言,如c++)是使用memcpy。