位操作 - rotateLeft

Question

目标是编写一种方法，仅使用 ~、!、|、&、^、+、>>、<<（无 for 循环）将 32 位机器中的 n 个位向左移动, if 语句，依此类推...)。我认为我所拥有的应该有效。我的问题是变量 move_left 似乎运行不正常。这是我的代码，它被分解成多个步骤以便我找出问题所在：

int rotateLeft(int x, int n) 
 {
     int move_left = (0x20 + (~n + 1)); // 32 - n
     int expr1 = x >> n; // chopping off n bits on the right
     int expr2 = ~((~0x0) << n); // n number of 1s on the right
     int expr3 = expr2 & x; // the bits that now need to be on the left
     int expr4 = expr3 << move_left; // the correct bits on the left
     int expr7 = ~0x0 << move_left; // breaking down expr5
     int expr5 = (~((~0x0) << move_left)); //
     int expr6 = expr5 & expr1; // copying the right sided body
     int result = expr6 | expr4; //adding the left side

     printf("%d\n%d\n%d\n%d\n%d\n%d\n", move_left, expr1, expr7, expr5, expr6, expr4);

     return result;
 }

使用 rotateLeft(-2147483648[0x80000000],0[0x0]) 进行测试时，结果不正确。在追查我的论点时，打印出来的是：

32
-2147483648
-1
0
0
0

我不明白 move_left 为什么是 32（这是正确的），但是 ~0x0 << move_left 不知何故是 -1，而它应该是 0！（当我在 expr7 中将 left_right 替换为 0x20 时，它会正确打印 0。）

感谢您的帮助！

Answer 1

你的代码对于左旋转任务来说真的很复杂。我在您的代码中看到的可能是一个数据类型的问题。当 signed int 被隐藏时，正确的符号位正在复制，例如傻瓜代码

    int x = 0x80000000;
    x >>=3;
    printf("%X\n", x);

打印结果：

F0000000

但是如果数据类型改为unsigned:

    unsigned int x = 0x80000000;
    x >>=3;
    printf("%X\n", x);

结果将是：

10000000

所以，试试十六进制输出，看看发生了什么，然后尝试使用无符号类型来改变位运算逻辑。

Answer 2

来自 C99 标准，第 6.5.7 (3) 条，关于移位运算符：

(...) If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

如您所见，这不是纯粹的理论问题；在某些平台上，操作数超出此范围的位移位操作可以做很多事情，因为以这种方式构建硬件 easier/faster/more efficient/required 更少 space 。但它并没有就此结束。 Quoth 6.5.7(4):

The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeroes. If E1 has an unsigned type, the value of the result is E1 x 2^E2, reduced modulo one more than the maximum value representable in the result type. If E1 has signed type and nonnegative value, and E1 x 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

和 (5):

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

通常，超出定义范围的带符号左移会表现出可预测的行为，并且通常会在带符号的右移上进行符号扩展（意味着负值移入 1，正值移入 0），但是您不能依赖于此。

长话短说：如果您尝试对有符号整数类型使用位移位，您将遇到麻烦。对所有内容使用 unsigned int，包括移位左侧的文字（例如，使用 ~0u 而不是 0）并注意您的右侧操作数保持在合法范围内。

那么，如果没有 if 和 ?:，你如何完成最后一点呢？一种方法是拆分班次：

 unsigned int expr1 = (x >> (n & 0xf)) >> (n & 0x10);
 unsigned int expr2 = ~((~0u << (n & 0xf)) << (n & 0x10));

这是有效的，因为 (n & 0xf) + (n & 0x10) == (n & 0x1f) 和 ((x >> a) >> b) == (x >> (a + b))。我在这里假设未签名 x，否则你需要一个演员表。

我可以想出更简单的向左旋转的方法，但是，好吧，这是你的功课。

位操作 - rotateLeft

Bit Manipulations - rotateLeft

c

bit-manipulation