6

所以我有一个任务,我必须在 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 的补码时得到不是负数(又名)0x7fffffff 的东西。它最终使情况变得更糟。请让我朝着正确的方向前进,我应该考虑什么,为什么?

4

2 回答 2

5

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

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

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

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

于 2013-10-05T22:33:37.543 回答
0

如果没有设置符号位,(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;

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

我想你说输入域被限制为一个字节。同样的想法也适用,但常数不同。

于 2013-10-05T22:19:29.323 回答