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

Question

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

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

根据this explanation，旋转可以通过以下实现来完成。

#include<stdio.h>
#define INT_BITS 32

/*Function to left rotate n by d bits*/
int leftRotate(int n, unsigned int d)
{
   /* In n<<d, last d bits are 0. To put first 3 bits of n at
     last, do bitwise or of n<<d with n >>(INT_BITS - d) */
   return (n << d)|(n >> (INT_BITS - d));
}

Answer 2

基本上你所要做的就是：

使用右移将所有内容右移 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。

如果您为移位传递一个负整数，它将无法正常工作，因为它会对最左边的位进行符号扩展。如果您希望此函数适用于所有整数，则应将所有类型从 int 更改为 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);
}

Answer 3

旋转是通过左右移动的组合完成的。

移动有符号整数的符号位是个问题。建议转换为 unsigned 以执行移位。 @The Paramagnetic Croissant

An example of implementation-defined behavior is the propagation of the high-order bit when a signed integer is shifted right.

移位位宽或更多是个问题。将实际移动限制为 n modulo Bit_width。当 n == 0.

时，OP 的 (...<<(32-n)); 代码是一个问题

OP 的示例看起来更像是左旋转。将假设函数应该向右旋转。 (0x87654321,4) --> 0x18765432。 @Mark Shevchenko

int 的宽度可能不是 32。

#include <limits.h>
#define INT_BIT_WIDTH (sizeof (int) * CHAR_BIT)

int rotateRight(int x, int n) {
  unsigned xu = x;
  unsigned nu = n;
  nu %= INT_BIT_WIDTH;
  unsigned y = xu >> nu;
  if (nu > 0) {
    y |= xu << (INT_BIT_WIDTH - nu);
  }
  return y;
}

[编辑] 由于 OP 仅限于 ~ & ^ | + << >>，请使用以下备用代码。
注意：在 int 的宽度不是 2 的幂的极少数情况下，这是一个问题。

// nu %= INT_BIT_WIDTH;
nu &= INT_BIT_WIDTH - 1;

[Edit2] 以为我会形成一个 unsigned 受@RPGillespie 启发的简约解决方案，因为 OP 不能使用 %.

#include <limits.h>
#define UNS_WIDTH    (sizeof (unsigned) * CHAR_BIT)
#define UNS_WIDTH_M1 (UNS_WIDTH - 1)

unsigned unsigned_rotate_right(unsigned x, unsigned n) {
  return (x >> (n & UNS_WIDTH_M1)) | (x << ((UNS_WIDTH - n) & UNS_WIDTH_M1));
}

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

Rotate right using bit operation in c

c

bit-manipulation

bit