如何在C++中可靠地执行算术右移?

13z8s7eq  于 2023-06-21  发布在  其他
关注(0)|答案(4)|浏览(146)

“算术右移”操作类似于正常(逻辑)右移,除了最高有效位 (即移入) 位填充有符号位而不是0。不幸的是,在C中(在C20之前,也在C中),对有符号整数执行右移的结果是[编译器/平台]实现定义的。
有没有一种方法可以执行“算术右移”,无论实现细节如何,都能保证提供正确的结果?理想情况下,代码足够简单,可以内联,并且不包含任何条件或分支。

dffbzjpn

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()编译为:

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
rkue9o1l

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或更高版本中,我们可以使用以下模板来处理任何有符号整数类型:

#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代码的答案是迂腐的。

oewdyzsn

oewdyzsn3#

直接对有符号整数使用>>即可。

主要的编译器都记录了它执行算术移位:

  • GCC
  • MSVC
  • Clang并没有完全记录实现定义的行为,但是由于它是GCC和MSVC的直接替代品,所以它也应该是安全的。

而且,正如你所说,C++20保证了>>的符号扩展。我相当肯定这只是标准化了编译器正在做的事情。
为了确定,添加一个测试:

static_assert(-4 >> 1 == -2, ">> doesn't do sign extension");
gtlvzcf8

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;
}

相关问题