2

我研究这个谜题已经有一段时间了。我试图弄清楚如何将数字 (x) 中的 4 位向左旋转（带环绕） n 其中 0 <= n <= 31 .. 代码将如下所示：

moveNib(int x, int n){
//... some code here
}

诀窍是我只能使用这些运算符：

~ & ^ | + << >>

而其中只有 25 个的组合。我也不能使用 If 语句、循环、函数调用。而且我只能使用 int 类型。

一个例子是 moveNib(0x87654321,1) = 0x76543218。

我的尝试：我已经想出了如何使用掩码来存储位，但我不知道如何移动任意数字。任何帮助将不胜感激，谢谢！

4

2 回答 2

4

怎么样：

uint32_t moveNib(uint32_t x, int n) { return x<<(n<<2) | x>>((8-n)<<2); }

它用于<<2从半字节转换为位，然后将位移动那么多。为了处理回绕，我们或通过在相反方向上移动了相反数量的数字的副本。例如，用x=0x87654321and n=1，左移 4 位变为0x76543210，右移 28 位变为0x00000008，并且当它们一起进行 OR 运算时，结果为0x76543218。

编辑：如果-真的不允许，那么这将得到相同的结果（假设一个具有二进制补码整数的架构）而不使用它：

uint32_t moveNib(uint32_t x, int n) { return x<<(n<<2) | x>>((9+~n)<<2); }

编辑2：好的。既然你不能使用任何东西int，那么这个怎么样？

int moveNib(int x, int n) { return (x&0xffffffff)<<(n<<2) | (x&0xffffffff)>>((9+~n)<<2); }

逻辑与以前相同，但我们通过与 进行与运算来强制计算使用无符号整数0xffffffff。不过，所有这些都假设为 32 位整数。我现在还有什么遗漏的吗？

Edit3：这是另一个版本，应该更便携：

int moveNib(int x, int n) { return ((x|0u)<<((n&7)<<2) | (x|0u)>>((9+~(n&7))<<2))&0xffffffff; }

n它按照 chux 的建议设置上限，并用于|0u转换为无符号数，以避免使用有符号整数获得符号位重复。之所以有效，是因为（根据标准）：

否则，如果无符号整数类型的操作数的等级大于或等于另一个操作数类型的等级，则将有符号整数类型的操作数转换为无符号整数类型的操作数的类型。

由于int和0u具有相同的秩，但是0u是无符号的，因此结果是无符号的，即使与 0 进行 ORing 否则将是一个空操作。

然后它将结果截断为 32 位的范围，int以便如果 int 的位数超过此值，该函数仍然可以工作（尽管在这种情况下仍将在最低 32 位上执行轮换。64 位版本将用 15 替换 7，用 17 替换 9 并使用 0xffffffffffffffff 截断）。

此解决方案使用 12 个运算符（如果您跳过截断，则为 11 个，如果您存储n&7在变量中，则为 10 个）。

要详细了解此处发生的情况，让我们通过您给出的示例来了解它：x=0x87654321, n=1. x|0u结果是一个无符号数0x87654321u。(n&7)<<2=4，所以我们将左移 4 位，而((9+~(n&7))<<2=28，所以我们将右移 28 位。所以把这些放在一起，我们将计算0x87654321u<<4 | 0x87654321u >> 28。对于 32 位整数，这是0x76543210|0x8=0x76543218. 但是对于 64 位整数，它是0x876543210|0x8=0x876543218，所以在这种情况下，我们需要截断为 32 位，这就是 final&0xffffffff所做的。如果整数短于 32 位，那么这将不起作用，但是您在问题中的示例有 32 位，所以我假设整数类型至少有那么长。

作为一个小旁注：如果您允许一个不在列表中的运算符，即sizeof运算符，那么我们可以制作一个自动处理更长 int 的所有位的版本。受 Aki 启发，我们得到（使用 16 个运算符（记住，sizeof是 C 中的运算符））：

int moveNib(int x, int n) {
    int nbit = (n&((sizeof(int)<<1)+~0u))<<2;
    return (x|0u)<<nbit | (x|0u)>>((sizeof(int)<<3)+1u+~nbit);
}
于 2014-03-02T02:36:15.010 回答
3

如果没有额外的限制，典型的 rotate_left 操作（0 < n < 32）是微不足道的。

uint32_t X = (x << 4*n) | (x >> 4*(8-n));

由于我们谈论的是旋转，所以n < 0 不是问题。向右旋转 1 与向左旋转 7 个单位相同。IE。nn=n & 7;我们已经完成了。

int nn = (n & 7) << 2;                         // Remove the multiplication
uint32_t X = (x << nn) | (x >> (32-nn));

当 时nn == 0，x 将移动 32，这是未定义的。这可以简单地替换为x >> 0，即根本没有旋转。(x << 0) | (x >> 0) == x.

用加法代替减法： a - b = a + (~b+1)并简化：

int nn = (n & 7) << 2;
int mm = (33 + ~nn) & 31;
uint32_t X = (x << nn) | (x >> mm);    // when nn=0, also mm=0

现在唯一的问题是右移有符号的 int x，这会复制符号位。应该通过面膜治愈：(x << nn) - 1

int nn = (n & 7) << 2;
int mm = (33 + ~nn) & 31;
int result = (x << nn) | ((x >> mm) & ((1 << nn) + ~0));

至此，我们只使用了 12 个允许的操作——接下来我们可以开始深入研究 sizeof(int) 的问题......

int nn = (n & (sizeof(int)-1)) << 2; // etc.
于 2014-03-02T12:40:51.583 回答