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,并继续旋转,这将无效.)