仅使用“〜＆^ | + << >> =“和20个运算符来实现逻辑右移

Question

因此，我有一项工作，我必须在c中编写仅使用〜，＆，^和|的按位运算的函数。，+，<<，>>和=。我只需要使用20个操作。而且我不允许使用控制结构，例如if-else，for，while，switch或其他在条件块中执行代码的东西。同样，类型转换也已结束，并且未在函数头中声明的字节（已提供给我）限制为1个字节或8位值；所以我的十六进制数为0到FF。

我必须编写的函数是逻辑右移。因此，与其用符号位填充它们，不如用0填充

这是我所做的：

int logicalShift(int x, int n) {
    int op=0xFFFFFFFF;
    int tcn=(~n+1);
    int sizeshift=0x20 & tcn;
    op=(op<<sizeshift);
    return ((x>>n) + (op));
}

这就是我期望得到的结果（对于x = 0x80000000和n = 0x01），我期望得到0x40000000，即十进制的1073741824。这就是我得到的。但是（对于x = 0x80000000和n = 0x0，我希望得到0x80000000，但是我得到0x7fffffff，这是我的答案减去一点。我可以加上一点，但是它弄乱了第一个答案。所以我在做什么错了我有一个案子，但没有另一个，我也尝试过。

int logicalShift(int x, int n) {
    int op=0xFFFFFFFF;
    int tcn=(~n+1);
    int sizeshift=0x20 & tcn;
    op=(op<<sizeshift);
    return ((x>>n) + (op  ^ ~n));
}

我以为，如果我对0的情况下的位进行异或运算，以将全为1的符号位清零，那么在经过编译器转换为2的补码时，我得到的结果将不是负数（aka）0x7fffffff。最终使情况变得更糟。请设定正确的方向，我应该考虑什么，为什么？

Answer 1

逻辑移位和算术移位之间的区别在于从左移入的位。要在算术方面实现逻辑移位，您可以进行算术移位，然后清除新位。在伪代码中：

1. 生成一个掩码，当与结果进行 AND 运算时将清除最左边的n位。
2. 右移n位。
3. 和面具。

使用 AND 意味着您不必关心移入了哪些位。您只想无条件地将它们设置为 0。

那么问题是如何生成掩码。我将把它留给你作为练习。

Answer 2

如果未设置符号位，(x >> n) == (x >>> n). 如果设置了符号位，我们在进行移位之前将其屏蔽，然后将其添加回来：(x & 0x7FFFFFFF) >> n | (0x40000000 >> (n - 1))。

如果我们知道这两种情况中的哪一种，计算就会变得更容易。如果我们可以使用if，我们就可以将这两种情况结合起来。我们必须模拟一个条件。

int signBit1 = (x & 0x7FFFFFFF) >> n | (0x40000000 >> (n - 1));
int signBit0 = x >> n;
var signBitIsolated = x & 0x80000000; // either 0 or 0x80000000
var signMask = signBitIsolated >> 31; //either 0 or 0xFFFFFFFF
var combined = (signBit0 & ~signMask) | (signBit1 & signMask);
return combined;

我们通过生成全零或全一掩码并对两种情况进行或运算来模拟条件。

我想你说过输入域仅限于一个字节。同样的想法也适用，但常数不同。