c - C 中的位循环

Question

问题:C 程序设计语言的练习 2-8，“编写一个函数 rightrot(x,n) 返回整数 x 的值，向右旋转 n 个位置。”

我已经用我知道的每一种方式做到了这一点。这是我遇到的问题。为这个练习取一个给定的数字，比如 29，然后将它向右旋转一个位置。
11101，它变为 11110 或 30。为了论证，假设我们正在处理的系统具有 32 位的无符号整数类型大小。进一步说，我们将数字 29 存储在一个无符号整数变量中。在内存中，数字前面会有 27 个零。因此，当我们使用下面发布的几种算法之一向右旋转 29 时，我们得到数字 2147483662。这显然不是想要的结果。

unsigned int rightrot(unsigned x, int n) {
    return (x >> n) | (x << (sizeof(x) * CHAR_BIT) - n);
}

从技术上讲，这是正确的，但我认为 11101 前面的 27 个零微不足道。我还尝试了其他几种解决方案:

int wordsize(void) {    // compute the wordsize on a given machine...
    unsigned x = ~0;
    int b;
    for(b = 0; x; b++)
        x &= x-1;
    return x;
}

unsigned int rightrot(unsigned x, int n) {
    unsigned rbit;
    while(n --) {
        rbit = x >> 1;
        x |= (rbit << wordsize() - 1);
    }
    return x;

这最后一个也是最终的解决方案是我认为我拥有它的那个，我将在我结束时解释它失败的地方。我相信您会看到我的错误...

int bitcount(unsigned x) {
    int b;
    for(b = 0; x; b++)
        x &= x-1;
    return b;
}

unsigned int rightrot(unsigned x, int n) {
    unsigned rbit;
    int shift = bitcount(x);
    while(n--) {
        rbit = x & 1;
        x >>= 1;
        x |= (rbit << shift);
    }
}

此解决方案给出了我一直在寻找的预期答案 30，但是如果您对 x 使用一个数字，例如 31 (11111)，那么就会出现问题，特别是结果是 47，对 n 使用一个数字。我之前没有想到这一点，但如果使用像 8 (1000) 这样的数字，那就太困惑了。 8 中只有一个设置位，因此移位肯定是错误的。在这一点上，我的理论是前两个解决方案是正确的(大部分)，我只是遗漏了一些东西......

Answer 1

按位旋转总是必须在给定宽度的整数范围内。在这种情况下，假设您是一个 32 位整数，2147483662 (0b10000000000000000000000000001110) 确实是正确答案；你没有做错任何事!

0b11110 不会被任何合理的定义视为正确的结果，因为继续使用相同的定义向右旋转它永远不会返回原始输入。 (考虑到另一个右旋转会得到 0b1111，继续旋转不会有任何效果。)