如何在 5 位表示上模拟二进制补码运算？

Question

假设必须按以下编码对两个有符号数求和（或相减等）：

short short_sum (int i1, int i2) {
    assert (SHRT_MIN <= i1 && i1 <= SHRT_MAX);
    assert (SHRT_MIN <= i2 && i2 <= SHRT_MAX);
    return (short)(i1 + i2);
    }

我需要模拟相同的效果，但分别用有符号字节和（理论上的）5 位有符号整数替换 int 和 short。类似下面的内容：

signed char tiny_sum (signed char c1, signed char c2) {
    assert (-16 <= c1 && c1 <= 15);
    assert (-16 <= c2 && c2 <= 15);
    return (signed char)(((c1 + c2) << (CHAR_BIT - 5)) >> ((CHAR_BIT - 5)));
    }

虽然上面的代码已经成功了，但它有一些缺陷：右移负数是实现定义的，更糟糕的是，左移这样的数字，或者左移“溢出”的正数, 未定义。所以代码既不可移植也不能真正预测。

所以这是我的问题：我怎样才能通过快速、便携和定义明确的位操作达到预期的效果？

提前致谢。

Answer 1

使用https://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtend做：

#include <stdio.h>

// start with good typedefs...
typedef signed char int5_t;
typedef unsigned char uint5_t;
#define INT5_MAX 15
#define INT5_MIN -16
#define UINT5_MAX 31

int5_t int5_add(int5_t a, int5_t b) {
    // converting signed to unsigned is defined
    // `% 32` is just the same as `& 0x1f`.
    const unsigned c = ((unsigned)a + (unsigned)b) % 32;
    // Just copying from the link...
    const unsigned m = 1U << (5 - 1);
    // Just two operations.
    return (c ^ m) - m;
}

void test(int a, int b, int c) {
    int d = int5_add(a, b);
    printf("%3hhd + %3hhd = %3hhd shouldbe %3hhd - %s\n", a, b, d, c, d == c ? "OK" : "ERROR");
}
int main() {
    test(-16, -1, 15);
    test(-16, 0,  -16);
    test(-16, 1,  -15);
    test(15,  1,  -16);
    test(15,  0,  15);
    test(15,  -1, 14);
    return -1;
}

and, worse, left-shifting such a number, or a positive whose left-shifting "overflows", is undefined

标准中的“未定义”，但请参阅您的编译器文档。在 gcc 我们“知道” integers implementation:

GCC supports only two’s complement integer types, and all bit patterns are ordinary values.

[...]

The results of some bitwise operations on signed integers (C90 6.3, C99 and C11 6.5).

Bitwise operators act on the representation of the value including both the sign and value bits, where the sign bit is considered immediately above the highest-value value bit. Signed ‘>>’ acts on negative numbers by sign extension.

As an extension to the C language, GCC does not use the latitude given in C99 and C11 only to treat certain aspects of signed ‘<<’ as undefined. However, -fsanitize=shift (and -fsanitize=undefined) will diagnose such cases. They are also diagnosed where constant expressions are required.

如何在 5 位表示上模拟二进制补码运算？

How to simulate two's complement arithmetics upon 5-bit representation?

c

bit-manipulation

twos-complement