c - 16 位非负数的右旋？

Question

我正在研究一种需要执行正确旋转的方法。比如我有一个二进制数0101110111000111，执行该方法后结果应该是1010111011100011。传入一个16位非负数作为参数，这个参数值会将所有位右移移动 1 位，并将低位移动到高位(如上例)。

这是我写的代码。我将 0101110111000111 转换为十进制值 24007。

#include <stdlib.h>
#include <stdio.h>

unsigned int rotateRight(unsigned int x);

int main(int argc, char **argv) {
  unsigned int n = 24007; 
  printf("%d\n", rotateRight(n, d)); 
  return 0; 
} 

/*Function to right rotate n by d bits*/
unsigned int rotateRight(unsigned int x) {
  return (x >> 1) | (x << (16-1));
}

我的预期结果应该是 44771 的值，因为它的十进制等于 1010111011100011。但是，当我运行这个程序时，我得到 786673379。有人可以解释为什么会这样，以及我如何改进我的旋转功能这样我就能得到正确答案？

Answer 1

(x << (16-1)将整个 16 位数量向左移动 15 位并将其添加到 x >> 1 之前.自 int可以保存 32 位值，因此不会截断您的计算，结果您会得到一个 31 位值。

即

x = 0101 1101 1100 0111
x >> 1 = 0010 1110 1110 0011
x << (16 -1) = 0010 1110 1110 0011 1000 0000 0000 0000

=> (x >> 1) | (x << (16-1))
    = 0101110111000111010111011100011 (binary)
    = 786673379 (decimal)

一个解决方案是:

unsigned int rotateRight(unsigned int x) {
  return ((x >> 1) | (x << (16-1))) & 0xffff;
}

即执行您已经在执行的计算，但只保留最低的 16 位。

或者，您可以使用类似 uint16_t 的类型以确保自动截断较大的数字，具体取决于您对隐式类型转换和显式类型转换语法的感受。