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，但如果你用像31（11111）这样的数字来代替x，会有问题，具体来说，当n为1时结果是47。我之前没有考虑到这一点，但如果使用8（1000）这样的数字，则会出现混乱。8中只有一个设置的位，因此移位肯定会出错。我目前的理论是前两个解决方案是正确的（大部分），我只是漏掉了什么...

- Brandon

---

我理解为前两个例子的行为是正确的，我没有疯掉。 - Brandon

我不确定你对于2147483662是错误答案的假设是否正确。在我看来，这个答案似乎是正确的！问题中确实提到了“整数x”，这意味着x有一定数量的比特位，例如32位。否则，rightrot(1,1)总是应该返回1吗？ - Mr Lister

Lister先生，我完全认输了。显然，我对二进制的概念、存储方式以及解释方式存在一些误解。我原本以为值是错误的，因为我认为在我在内存中使用的值之前的27个零对该值不重要。我明白你所说的关于“1”的意思。如果rightrot（1,1）总是返回1，那么如何左旋转像1000或10000000000000000000000000000000这样的数字呢？ - Brandon

注意到您的字长函数中有一个错别字。应该返回 b; 而不是返回 x;。 - user2927392

Answer 1

一个按位旋转操作通常都是在给定宽度内的整数范围内完成的。在这种情况下，假设你正在使用32位整数，则2147483662 (0b10000000000000000000000000001110) 确实是正确的答案，你没有做错任何事情！

根据任何合理的定义，0b11110 都不会被认为是正确的结果，因为继续使用同样的定义向右旋转它永远不会得到原始输入。 （考虑另一个向右旋转将会得到 0b1111，并继续旋转将没有任何效果。）

- user149341

---

我花了将近十个小时才妥协并寻求帮助。我觉得我快要失去理智了，不过我确实学到了一些东西，至少现在我知道我的理智和做简单数学的能力都还好。谢谢你。 - Brandon

我确实能看到问题。例如，这个问题没有提到整数是16位还是32位，而在这种情况下这是一个非常重要的区别：结果会有所不同。有符号整数也是如此：对奇数进行ROT操作将产生负结果。因此，思考这个问题而不是简单地编写程序例程是很好的。 - Mr Lister

Answer 2

在我看来，紧接着这个练习的书中部分的精神是，读者在不知道整数（以位为单位）或任何其他类型大小的情况下完成此问题。该部分的示例不需要那些信息；我认为练习也不需要。

尽管如此，在第2.9节之前，该书还没有介绍sizeof运算符，因此计算类型大小的唯一方法是手动“逐位”计数。

但我们不需要费心去做。我们可以通过每次旋转一个位来在n步内进行位旋转，而不管数据类型中有多少位。

仅使用该书到第2.9节所涵盖的语言部分，以下是我的实现（采用整数参数，按照练习要求返回整数）：循环n次，每次迭代x >> 1；如果x的旧低位为1，则设置新高位。

int rightrot(int x, int n) {
    int lowbit;

    while (n-- > 0) {
        lowbit = x & 1;            /* save low bit */
        x = (x >> 1) & (~0u >> 1); /* shift right by one, and clear the high bit (in case of sign extension) */
        if (lowbit)
            x = x | ~(~0u >> 1);   /* set the high bit if the low bit was set */
    }

    return x;
}

- momotaro

Answer 3

您可以使用二分查找来找到32位值中第一个 '1' 的位置。然后注意LSB位置的位，将该值右移所需的位数，并将LSB位放在第一个 '1' 的位置。

- user191776

---

我曾考虑使用二分查找，但书中声称练习可以使用提供给你的信息来回答。作者直到书后才讨论排序/搜索的细节。 - Brandon

我同意@duskwuff的观点；你真的不应该这样做。 - user191776

Answer 4

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

unsigned rightrot(unsigned x,int n) {
   int b = bitcount(x);
   unsigned a = (x&~(~0<<n))<<(b-n+1);
   x>> = n;
   x| = a;
}

- shivani jain

---

如果我们想将10101011向左旋转3位，得到01110101，则只需执行01100000 | 00010101。要获得01100000，我们执行（x＆〜（0 << n））<<（b-n + 1）。要获得0010101，我们执行x >> n。 - shivani jain