算术右移实现rightrot循环右移为何二次调用结果异常？

问题背景 #

在完成K&R的习题2-8（编写rightrot(x,n)返回整数x循环右移n位的结果）时：

• 基于掩码实现的rightrot函数运行正常
• 尝试用算术右移实现更简洁可移植的testrot函数时，出现异常：
  • 首次调用testrot(22, 3)结果正确
  • 将该返回值再次传入testrot（右移__INT_WIDTH__-3位）时结果错误
• 通过LLDB调试发现，第二次调用时testrot中的t值为-2，而正确实现中的t值应为6
• 把testrot的逻辑转换成Python脚本后运行正常，无法定位C语言代码的问题

问题根源 #

核心差异在于C语言有符号整数的算术右移规则和Python的任意精度整数模型：

1. C语言中，有符号整数的算术右移会用符号位（最高位）填充空位。当x是负数（最高位为1）时，右移会不断补1，导致高位被符号位覆盖，无法正确提取原本的高位部分
2. 第二次调用时，传入的x是第一次循环右移后的结果，此时x的最高位可能为1（即负数）。算术右移__INT_WIDTH__-3位时，会生成全1的高位值（比如32位int下的0xFFFFFFFE，对应十进制-2），而正确的高位提取应该是原数的高3位（即6）
3. Python的int是无固定宽度的任意精度类型，不存在符号位扩展的问题，移位逻辑本质上等价于无符号整数的处理，所以你的逻辑在Python中可以正常运行

修正方案 #

要在C语言中实现可移植的循环右移，必须规避符号位扩展的影响，以下是两种可行方案：

方案1：使用无符号整数处理 #

无符号整数的右移是逻辑右移（填充0），完全避免符号位问题：

#include <stdint.h>

unsigned int rightrot(unsigned int x, int n) {
    const int bits = sizeof(unsigned int) * 8;
    n %= bits;
    if (n == 0) return x;
    // 提取低n位移到高位
    unsigned int high_bits = x << (bits - n);
    // 右移n位得到低位部分
    unsigned int low_part = x >> n;
    return high_bits | low_part;
}

方案2：对有符号整数手动屏蔽符号位扩展 #

如果必须使用有符号整数，操作时先转为无符号类型再处理：

#include <limits.h>

int testrot(int x, int n) {
    n %= INT_WIDTH;
    if (n == 0) return x;
    // 提取低n位移到高位：转无符号避免符号位扩展
    int high_bits = (unsigned int)x << (INT_WIDTH - n);
    // 逻辑右移n位：转无符号后右移再转回有符号
    int low_part = (unsigned int)x >> n;
    return high_bits | low_part;
}

内容的提问来源于stack exchange，提问作者Angus Hay