11

首先，不，这不是我的作业，这是一本名为Computer Systems A Programmer's Perspective的书的实验室（顺便说一句，优秀的书）

我需要在不使用以下任何内容的情况下对有符号整数执行逻辑右移：

  • 铸件
  • if, while, switch, for, do- while,? :
  • 任何类型的指针

允许的运算符是： ! + ~ | >> << ^

到目前为止我尝试了什么？

/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
    int mask = ~0;
    int shiftAmount = 31 + ((~n)+1);//this evaluates to 31 - n on two's complement machines
    mask = mask << shiftAmount;
    mask = ~mask;//If n equals 0, it means we have negated all bits and hence have mask = 0
    x = x >> n;
    return x & mask; 
}

只要n不等于就可以正常工作0，当它这样做时，此代码会中断，因为掩码将变为全 0，并且函数将返回0。

我将不胜感激任何正确方向的提示，而不是完整的代码。

同样，这不是功课；实验室作业可在此处公开获取http://csapp.cs.cmu.edu/public/labs.html

PS：不是重复的，不要发布涉及转换为未签名然后转移的解决方案。

4

2 回答 2

6

这个问题是在 C++ 中搜索逻辑移位的第一个结果。

因此，回答允许强制转换的一般情况也是有意义的- 因为此处显示的代码均未使用正确（且快速）的操作码（仅一条shr指令而不是sar）。

演员表

此版本也适用于即将推出的int128_t（目前__int128在 GCC、Clang 和 ICC 中）和其他未来类型。如果您被允许使用type_traits并且您的代码应该在将来工作而不考虑正确的无符号类型，那么您应该将它用于正确的强制转换。

代码

#include <type_traits>

template<class T>
inline T logicalShift(T t1, T t2) {
  return 
    static_cast<
      typename std::make_unsigned<T>::type
    >(t1) >> t2;
}

汇编代码分析

将其打包成f(T x, T y) { return logicalShift(x, y); }以下汇编程序指令（GCC9.2，-O3）的结果：

f(int, int):
        mov     eax, edi
        mov     ecx, esi
        shr     eax, cl
        ret
f(unsigned int, unsigned int):
        mov     eax, edi
        mov     ecx, esi
        shr     eax, cl
        ret
f(__int128, __int128):
        mov     rcx, rdx
        mov     rax, rdi
        mov     rdx, rsi
        shrd    rax, rsi, cl
        shr     rdx, cl
        xor     esi, esi
        and     ecx, 64
        cmovne  rax, rdx
        cmovne  rdx, rsi
        ret
f(unsigned __int128, unsigned __int128):
        mov     rcx, rdx
        mov     rax, rdi
        mov     rdx, rsi
        shrd    rax, rsi, cl
        shr     rdx, cl
        xor     esi, esi
        and     ecx, 64
        cmovne  rax, rdx
        cmovne  rdx, rsi
        ret

结果T a, b; T c = a >> b;：

f(int, int):
        mov     eax, edi      # 32-bit registers
        mov     ecx, esi
        sar     eax, cl       # lower 8-bit of cx register
        ret
f(long, long):
        mov     rax, rdi      # 64-bit registers
        mov     ecx, esi
        sar     rax, cl
        ret
f(unsigned int, unsigned int):
        mov     eax, edi
        mov     ecx, esi
        shr     eax, cl
        ret
f(__int128, __int128):
        mov     rcx, rdx
        mov     rdx, rsi
        mov     rax, rdi
        sar     rdx, cl
        shrd    rax, rsi, cl
        mov     rsi, rdx
        sar     rsi, 63
        and     ecx, 64
        cmovne  rax, rdx
        cmovne  rdx, rsi
        ret

我们看到，区别主要只是shr代替sar（对于__int128还有一些）。什么代码可以更快？

无演员版本

（将指令集简化为 ~ & ^ | + << >>）

问题 - 左移 ( SAL, SHL)

@Fingolfin 最初的想法很好。但是我们的处理器不会做我们首先想到的事情int mask = ~0 << n，n >= 32;但是为什么呢？

C++ 标准（草案 N4713, 8.5.7, 2nd）说 <<:

的值E1 << E2是E1左移的E2位位置；空出的位是零填充的。如果E1具有无符号类型，则结果的值为 ，以E1 × 2^E2比结果类型中可表示的最大值大一为模减少。否则，如果E1具有带符号类型和非负值，并且E1 × 2^E2可以在结果类型的相应无符号类型中表示，则转换为结果类型的该值就是结果值；否则，行为是 undefined。

听起来像(E1 << E2) % (UINTxx_MAX + 1)，我们只是从右边填充 0 并用模运算切断前导位。简单明了。

分析左移

16 位短、32 位整数和 64 位长的汇编代码（GCC 9.2，-O3）是：

g(short, short):
        movsx   eax, di    # 16-bit to 32-bit register
        mov     ecx, esi
        sal     eax, cl    # 1st is 32-bit, 2nd is 8-bit register
        ret
g(int, int):
        mov     eax, edi   # 32-bit registers
        mov     ecx, esi
        sal     eax, cl    # 1st is 32-bit, 2nd is 8-bit register
        ret
g(long, long):
        mov     rax, rdi   # 64-bit registers
        mov     ecx, esi
        sal     rax, cl    # 1st is 64-bit, 2nd is 8-bit register
        ret

所以，我们讨论了我们从~0 << ifor断言的int i = 0; i <= 33; i++内容，但我们真正得到了什么？

 0: 11111111111111111111111111111111
 1: 11111111111111111111111111111110
 2: 11111111111111111111111111111100
 3: 11111111111111111111111111111000
 4: 11111111111111111111111111110000
 5: 11111111111111111111111111100000
 6: 11111111111111111111111111000000
 7: 11111111111111111111111110000000
 8: 11111111111111111111111100000000
 9: 11111111111111111111111000000000
10: 11111111111111111111110000000000
11: 11111111111111111111100000000000
12: 11111111111111111111000000000000
13: 11111111111111111110000000000000
14: 11111111111111111100000000000000
15: 11111111111111111000000000000000
16: 11111111111111110000000000000000
17: 11111111111111100000000000000000
18: 11111111111111000000000000000000
19: 11111111111110000000000000000000
20: 11111111111100000000000000000000
21: 11111111111000000000000000000000
22: 11111111110000000000000000000000
23: 11111111100000000000000000000000
24: 11111111000000000000000000000000
25: 11111110000000000000000000000000
26: 11111100000000000000000000000000
27: 11111000000000000000000000000000
28: 11110000000000000000000000000000
29: 11100000000000000000000000000000
30: 11000000000000000000000000000000
31: 10000000000000000000000000000000
32: 11111111111111111111111111111111
33: 11111111111111111111111111111110

我们看到，结果更像~0 << (i%2^5).

所以，看一下 long（long aka.int64_t）案例：（用 MSVC for x86 编译）

 0: 1111111111111111111111111111111111111111111111111111111111111111
 1: 1111111111111111111111111111111111111111111111111111111111111110
 2: 1111111111111111111111111111111111111111111111111111111111111100
 3: 1111111111111111111111111111111111111111111111111111111111111000
 4: 1111111111111111111111111111111111111111111111111111111111110000
 5: 1111111111111111111111111111111111111111111111111111111111100000
 6: 1111111111111111111111111111111111111111111111111111111111000000
 7: 1111111111111111111111111111111111111111111111111111111110000000
 8: 1111111111111111111111111111111111111111111111111111111100000000
 9: 1111111111111111111111111111111111111111111111111111111000000000
10: 1111111111111111111111111111111111111111111111111111110000000000
11: 1111111111111111111111111111111111111111111111111111100000000000
12: 1111111111111111111111111111111111111111111111111111000000000000
13: 1111111111111111111111111111111111111111111111111110000000000000
14: 1111111111111111111111111111111111111111111111111100000000000000
15: 1111111111111111111111111111111111111111111111111000000000000000
16: 1111111111111111111111111111111111111111111111110000000000000000
17: 1111111111111111111111111111111111111111111111100000000000000000
18: 1111111111111111111111111111111111111111111111000000000000000000
19: 1111111111111111111111111111111111111111111110000000000000000000
20: 1111111111111111111111111111111111111111111100000000000000000000
21: 1111111111111111111111111111111111111111111000000000000000000000
22: 1111111111111111111111111111111111111111110000000000000000000000
23: 1111111111111111111111111111111111111111100000000000000000000000
24: 1111111111111111111111111111111111111111000000000000000000000000
25: 1111111111111111111111111111111111111110000000000000000000000000
26: 1111111111111111111111111111111111111100000000000000000000000000
27: 1111111111111111111111111111111111111000000000000000000000000000
28: 1111111111111111111111111111111111110000000000000000000000000000
29: 1111111111111111111111111111111111100000000000000000000000000000
30: 1111111111111111111111111111111111000000000000000000000000000000
31: 1111111111111111111111111111111110000000000000000000000000000000
32: 1111111111111111111111111111111100000000000000000000000000000000
33: 1111111111111111111111111111111000000000000000000000000000000000
34: 1111111111111111111111111111110000000000000000000000000000000000
35: 1111111111111111111111111111100000000000000000000000000000000000
36: 1111111111111111111111111111000000000000000000000000000000000000
37: 1111111111111111111111111110000000000000000000000000000000000000
38: 1111111111111111111111111100000000000000000000000000000000000000
39: 1111111111111111111111111000000000000000000000000000000000000000
40: 1111111111111111111111110000000000000000000000000000000000000000
41: 1111111111111111111111100000000000000000000000000000000000000000
42: 1111111111111111111111000000000000000000000000000000000000000000
43: 1111111111111111111110000000000000000000000000000000000000000000
44: 1111111111111111111100000000000000000000000000000000000000000000
45: 1111111111111111111000000000000000000000000000000000000000000000
46: 1111111111111111110000000000000000000000000000000000000000000000
47: 1111111111111111100000000000000000000000000000000000000000000000
48: 1111111111111111000000000000000000000000000000000000000000000000
49: 1111111111111110000000000000000000000000000000000000000000000000
50: 1111111111111100000000000000000000000000000000000000000000000000
51: 1111111111111000000000000000000000000000000000000000000000000000
52: 1111111111110000000000000000000000000000000000000000000000000000
53: 1111111111100000000000000000000000000000000000000000000000000000
54: 1111111111000000000000000000000000000000000000000000000000000000
55: 1111111110000000000000000000000000000000000000000000000000000000
56: 1111111100000000000000000000000000000000000000000000000000000000
57: 1111111000000000000000000000000000000000000000000000000000000000
58: 1111110000000000000000000000000000000000000000000000000000000000
59: 1111100000000000000000000000000000000000000000000000000000000000
60: 1111000000000000000000000000000000000000000000000000000000000000
61: 1110000000000000000000000000000000000000000000000000000000000000
62: 1100000000000000000000000000000000000000000000000000000000000000
63: 1000000000000000000000000000000000000000000000000000000000000000
64: 0000000000000000000000000000000000000000000000000000000000000000
65: 0000000000000000000000000000000000000000000000000000000000000000

繁荣！

（直到 31 在 GCC 中也保持简短，因为它使用 32 位EAX寄存器sal）

但是，此结果仅由编译器创建：

x86 msvc v19.22 , /O2: 
_x$ = 8                                       ; size = 8
_y$ = 16                                                ; size = 8
__int64 g(__int64,__int64) PROC                                  ; g, COMDAT
        mov     eax, DWORD PTR _x$[esp-4]
        mov     edx, DWORD PTR _x$[esp]
        mov     ecx, DWORD PTR _y$[esp-4]
        jmp     __allshl
__int64 g(__int64,__int64) ENDP
x64 msvc v19.22 , /O2: 
x$ = 8
y$ = 16
__int64 g(__int64,__int64) PROC                                  ; g, COMDAT
        mov     rax, rcx
        mov     rcx, rdx
        shl     rax, cl
        ret     0
__int64 g(__int64,__int64) ENDP

并且 x64 MSVC 代码显示与 GCC 9.2 代码相同的行为 - 使用shl而不是sal.

从那时起，我们现在知道处理器本身（英特尔酷睿第六代）仅使用cl寄存器的最后一位，这取决于移位操作的第一个寄存器的长度，即使 C++ 标准另有规定。

一个小修复

所以，这就是代码中断的地方。本能地我会采取 shiftAmount of32 - n并进入上层问题，您已经通过使用 a shiftAmountof避免了这种情况31 - n。知道 n 是 0..31，没有 shiftAmount 32。很好。

但是，一方面减少意味着另一方面增加。现在mask需要从-2（我们不换档0b1111，我们换档0b1110）开始：

int logSh3(int x, int n) {
    int mask = ~2 + 1;
    int shiftAmount = 31 + ((~n) + 1);//this evaluates to 31 - n on two's complement machines
    mask = mask << shiftAmount;
    mask = ~mask;//If n equals 0, it means we have negated all bits and hence have mask = 0
    x = x >> n;
    return x & mask;
}

它有效！

备用代码和分析

芬国昐密码（固定）

上层代码，作为汇编程序（GCC 9.2，-O3）：

logSh3(int, int):
        mov     ecx, 31
        mov     edx, -2
        mov     eax, edi
        sub     ecx, esi
        sal     edx, cl
        mov     ecx, esi
        not     edx
        sar     eax, cl
        and     eax, edx
        ret

9 条指令

哈罗德密码

int logSh2(int x, int n) {
    int shiftAmount = 31 + ((~n) + 1);//this evaluates to 31 - n on two's complement machines
    int mask = 1 << shiftAmount;
    mask |= mask + ((~1) + 1);
    x = x >> n;
    return x & mask;
}

logSh2(int, int):
        mov     ecx, esi
        mov     r8d, edi
        mov     edi, -2147483648
        shr     edi, cl
        sar     r8d, cl
        lea     eax, [rdi-1]
        or      eax, edi
        and     eax, r8d
        ret

8条指令

我们能做得更好吗？

另一种解决方案

代替左移，我们可以对 进行右移0b1000，将其向后移一并反转。

int logSh4(int x, int n) {
    int mask = 0x80000000;
    mask = mask >> n;
    mask = mask << 1;
    mask = ~mask;//If n equals 0, it means we have negated all bits and hence have mask = 0
    x = x >> n;
    return x & mask;
}

logSh4(int, int):
        mov     ecx, esi
        mov     edx, -2147483648
        sar     edx, cl
        sar     edi, cl
        lea     eax, [rdx+rdx]
        not     eax
        and     eax, edi
        ret

7 指令

更好的方法？

让我们0b0111向右移动，向左移动一个并加 1。所以我们不用逆：

int logSh5(int x, int n) {
    int mask = 0x7fffffff;
    mask = mask >> n;
    mask = (mask << 1) | 1;
    x = x >> n;
    return x & mask;
}

logSh5(int, int):
        mov     ecx, esi
        mov     eax, 2147483647
        sar     eax, cl
        sar     edi, cl
        lea     eax, [rax+1+rax]
        and     eax, edi
        ret

还剩 6 条指令。美好的。（但简单的演员阵容仍然是实践中的最佳解决方案）

于 2019-08-22T11:58:48.303 回答
3

俗气的回答显然违反了问题的精神：强制转换1不是在 C 或 C++ 中进行类型转换的唯一方法

return (x | 0U) >> n;    // assumes int and unsigned are the same width

（用于 x86-64 GCC 的 Godbolt）。请注意，它还依赖于 withnegative 的实现定义的行为n==0，x因为这会留下符号位设置。但是在正常的 2 的补码实现中，无符号和 int 之间的转换只是保留了位模式以及正整数的值。使类型双关语显式memcpy而不是使用隐式类型转换可以使其更加健壮。

|运算符使用通常的算术转换规则使两个操作数具有相同的类型。我们可以使用它来隐式地转换为无符号的、围绕强制转换的人为限制的规则律师。

0U数字文字后缀不是强制转换，它只是无符号常量的简单语言语法。另一种选择是x & UINT_MAX或x | (~UINT_MAX)。或者更有趣的是，如果你知道的宽度小于int等于如果它更大，则为那些版本。unsigned0xffffffffintunsignedlonglong long

当然，unsigned tmp = x;也不是演员表，所以真的只是那样做吧！但这更清楚地只是一个愚蠢的规则律师来寻找有问题的漏洞，而不是预期的目的。

假设：

  • 这可能仅适用于 2 的补码，其中从有符号到无符号的转换不会修改对象表示的位模式。（相关：如何在保留原始位模式的同时将（int）转换为（unsigned int）？ -在将模归约应用于无符号之前，转换保留值，而不是位模式。）

  • unsigned int与 的宽度相同int，因此我们不会丢失任何位，并且不会符号扩展以1在逻辑右移之前引入高位。**

例如(x | 0ULL) >> n不起作用；这将在逻辑右移之前将符号扩展到 64 位（或其他），因此结果的低宽度将有效地将符号位的副本移入。（假设 2 的补码。）xint

解决方法：使用无符号位域，其非填充位的确切数量为int. 有符号整数类型具有numeric_limits<T>::digits非符号位和 1 个符号位。（以及未知数量的填充）。这将需要分配，而不仅仅是与|.

struct uint { 
   unsigned long u : (1 + std::numeric_limits<int>::digits);
}

如果你想memcpy进入这个结构而不是赋值（例如，确保位模式在右移之前不会改变，在非 2 的补码系统上？）你可以用char pad[sizeof(int)];. 这绝对是矫枉过正，比必要的填充更多，使其至少与int（或其他方向所需的memcpy(&struct_tmp, &x, sizeof(x))）一样大。我不确定结构是否保证至少与 a 一样宽，unsigned long因为我们使用它作为位域的基本类型，我也必须仔细检查标准的那部分。不过，GCC 和 MSVC 就是这种情况。unsigned long long使其 sizeof 达到 8. IIRC，unsigned long保证至少与int.

如果我们想计算一个char[]数组所需的确切填充量，我们必须处理sizeof(int) - sizeof(unsigned)负数的可能性。但是计算另一个填充位域成员的额外位数可以工作，将填充计算为CHAR_BIT * sizeof(int) - (1 + digits)

在 C99 中，我们可以使用联合类型双关语来替换 memcpy，但我们可能仍然需要一个位域来确保我们将无符号值截断到正确的宽度。

脚注 1：ISO C++ 7.6.3 显式类型转换（强制转换表示法）[expr.cast]说：

2：可以使用函数表示法、类型转换运算符（dynamic_cast、static_cast、reinterpret_cast、const_cast）或强制转换表示法来表示显式类型转换。

    cast-expression:
        unary-expression
        ( type-id ) cast-expression

整个部分的名称是[expr.cast]，因此将这些用于类型转换的任何语法都视为强制转换是合理的，而不仅仅是“强制转换表达式”。幸运的是，没有必要试图证明unsigned(x) >> n不包括演员表是正当的。

于 2020-08-15T08:59:28.200 回答