在C语言中使用位运算向右旋转

Question

在C语言中使用位运算向右旋转

4

我正在尝试编写一个函数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; 
}

然而，我被禁止使用任何强制类型转换，只能使用以下操作符：~ & ^ | + << 和 >>。有谁可以帮我解决这个问题吗？

- paupau

禁止使用某些东西通常意味着这是一道作业题。你有没有被给出类似的例子（比如将其旋转到另一个方向）？ - jim mcnamara

2

看起来像是向左旋转。 :) - Mark Shevchenko

这是您的意思吗？例如，rotateRight(0x87654321,4) = 0x76543218和rotateRight(0x87654321,8) = 0x65432187？我已经找出如何执行此任务，但我不知道如何在没有强制转换的情况下完成它。 - paupau

2

我被禁止使用任何类型的强制转换 - 但是为什么你需要任何类型的强制转换呢？只需将参数和临时变量设置为unsigned，然后你就可以继续进行了。 - The Paramagnetic Croissant

关于%32的详细信息 - 是否应该尝试修复：some_int%32不是返回0-31的模运算，而是C余数操作符，在这种情况下返回-31到31。some_int%32u将为所有int编码实现“安全”缩减。 - chux - Reinstate Monica

3个回答

1

使用左移和右移的组合可以进行旋转。

移位有一个问题，那就是有符号整数的符号位会受到影响。建议先转换为unsigned类型再进行移位操作。@The Paramagnetic Croissant

实现定义的行为示例是：当带符号整数向右移位时，高位比特的传播方式。

向左或向右移超过位宽的比特也会导致问题。应将实际移位限制为n mod 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;
}

[编辑]由于原帖仅限使用 ~ & ^ | + << >>，请使用以下替代代码。
注意：这是一个罕见的问题，在int的宽度不是2的幂的情况下出现。

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

[编辑2] 我想出一个受@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));
}

- chux - Reinstate Monica

1

我注意到 OP 也不能使用 -，因此在假设我们使用的是二进制补码机器的情况下，将 - n 替换为 + (~n+1)。我不反对其他减号，因为它们可以在编译时求值。 - Iwillnotexist Idonotexist

0

根据这个解释，可以通过以下实现来进行旋转。

#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));
}

- Codor

2

应该写成 unsigned int n，否则左移操作可能会导致未定义的行为。 - mch

3

@mch，这甚至不是最大的问题！与在二进制补码计算机上（也就是绝大部分计算机）右移 n 时如果是负数它将进行符号扩展相比，这几乎是一个学术性的问题！ - Iwillnotexist Idonotexist

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gillespie · Accepted Answer

基本上，您需要做的就是：

使用右移位操作符 >> 将所有内容向右移动 n 位
将要旋转的位全部左移
使用或运算符 | 将右移和左移后的位组合起来

请参考以下代码示例，以了解如何使用您所需的函数签名实现此操作：

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);
}