在c中使用位操作向右旋转

Question

我正在尝试提出一个向右int rotateRight (int x, int n)旋转的函数。例如，xn

rotateRight(0x87654321,4) = 0x76543218

这是我到目前为止：

int rotateRight(int x, int n) {
  int mask = (((1 << n)-1)<<(32-n));
  int reserve = (int)((unsigned) (x&mask) >>(32-n));
  return (x << n) | reserve; 
}

但是，我被禁止使用任何强制转换，并且允许的操作是~ & ^ | + <<和>>。谁能帮我解决这个问题？

Answer 1

基本上你所要做的就是：

• 使用右移将所有内容右移 n 位： >>

• 将要旋转的位一直向左移动： <<

• 将右移和左移位与 组合or：|

有关使用您需要的函数签名的示例实现，请参阅此代码：

int rotateRight(int x, int n) {

    //if n=4, x=0x12345678:

    //shifted = 0x12345678 >> 4 = 0x01234567
    int shifted = x >> n;

    //rot_bits = (0x12345678 << 28) = 0x80000000
    int rot_bits = x << (32-n);

    //combined = 0x80000000 | 0x01234567 = 0x81234567
    int combined = shifted | rot_bits;

    return combined;
}

这种实现是不是安全的，虽然，至少在没有一些保障-即x永远是积极的，n将是积极和永远<= 32。

如果您传入一个负整数进行移位，它将无法正常工作，因为它将对最左边的位进行符号扩展。如果您希望此函数适用于所有整数，您应该将所有类型从intto更改为unsigned int（这样不会发生符号扩展或负左移），然后n对 32 ( % 32)取模。这是该函数的安全版本：

unsigned int rotateRight(unsigned int x, unsigned int n) {

    //needed so you don't right shift more than int width
    n %= 32;

    //needed so you don't left shift more than int width
    unsigned int leftshift_val = (32-n) % 32 

    unsigned int shifted = x >> n;
    unsigned int rot_bits = x << leftshift_val;
    unsigned int combined = shifted | rot_bits;

    return combined;
}

为您的极简主义者打高尔夫球：

unsigned rotr(unsigned x, unsigned n) {
    return (x >> n % 32) | (x << (32-n) % 32);
}