时间戳

首页 > 解决方案 > C 位圆移位 - 意外结果

c - C 位圆移位 - 意外结果

问题描述

我目前正在完成 K&R C 书籍练习，并且正在进行第 2 章的练习 8。挑战是编写一个函数“rotright”，将无符号整数 x 的位旋转（或循环移位） n 位。我相信我已经想出了一个解决方案，但它并没有返回我所期望的。给定二进制数213，向右11010101旋转2位将产生01110101，即117。但是，我的程序一经给出x=213并n=2返回53。我尝试在注释中写出二进制形式的整数发生的过程，但找不到问题。任何帮助，将不胜感激。

#include <stdio.h>

unsigned rotright(unsigned x, int n)
{
    /* Example with x = 11010101 (213 in decimal), n = 2
        First iteration:
            x = (01101010) | ~(11111111 >> 1) = 11101010
        Second iteration:
            x = (01110101) | ~(11111111 >> 0) = 01110101
        Returns 01110101

    right shifts only if last bit of x == 1, then sets first bit of right shifted x to 1
    if last bit of x == 0, x is right shifted by 1 and then unchanged.

    (01101010) | ~(11111111 >> (11010101 & 00000001))
    = 01101010 | ~(11111111 >> 00000001)
    = 01101010 | 10000000 = 11101010

    (11101010) | ~(11111111 >> (11101010 & 00000001))
    = 01110101 | ~(11111111 >> 0)
    = 01110101 | 00000000 = 01110101
    */
    for (; n > 0; n--)
        x = (x >> 1) | ~(~0 >> (x & 1));
    return x;
}

int main()
{
    printf("%d\n", rotright(213, 2));
    return 0; 
}

标签： cbit-manipulationbitwise-operators

解决方案

x = (x >> 1) | ~(~0 >> (x & 1));

你得到 53 因为这是 (213 >> 2)

~(~0 >> (x & 1))总是 0，因为 ~0 是-1，并且 (-1 >> n) 在你的情况下又是-1，最后 ~(-1) 是 0

你想要那个 ：

#include <stdio.h>
#include <limits.h>

unsigned rotright(unsigned x, int n)
{
   unsigned mask = (1u << (CHAR_BIT * sizeof(int) - 1));

  for (; n > 0; n--) {
    x = (x / 2) | ((x & 1) ? mask : 0);
  }
  return x;
}

int main()
{
    printf("%d\n", rotright(213, 2));
    return 0; 
}

在 32 位上，结果是 1073741877 是 1000000000000000000000000110101，而不是假设您在 8 位上工作的 117

推荐阅读