循环 移位 c语言

什么是循环移位？

循环移位与普通的逻辑移位不同,在普通移位中，被移出位的数值会被丢弃，而空出的位会被填充（通常是0或符号位）。

在循环移位中，被移出的一位或多位数值不会被丢弃，而是会从另一端补到空出的位置。

循环移位分为两种：

1. 循环左移

   • 操作：将数的所有位向左移动指定的位数。
   • 结果：从最左端（高位）移出的位，会依次补到最右端（低位）的空位上。
   • 示例：1101 循环左移 1 位 -> 1011 (最左边的 '1' 移到了最右边)

2. 循环右移

   • 操作：将数的所有位向右移动指定的位数。
   • 结果：从最右端（低位）移出的位，会依次补到最左端（高位）的空位上。
   • 示例：1101 循环右移 1 位 -> 1110 (最右边的 '1' 移到了最左边)

如何在 C 语言中实现循环移位？

C 语言标准库中并没有直接提供循环移位的函数（如 rol() 或 ror()），所以我们需要自己动手实现，最经典和通用的方法是使用 位运算。

核心思想

以一个 n 位的整数 x 进行 k 位循环左移为例：

1. 分离出要移动到末尾的部分：

   • 我们想把高 k 位移到低 k 位。
   • 可以先将 x 左移 k 位，这会把高 k 位移出，低 k 位变为 0。
   • x = 1101 (13), k = 1。x << 1 得到 1010 (10)。

2. 分离出要移动到开头的部分：

   • 我们想把低 n-k 位移到高 n-k 位。
   • 可以先将 x 右移 n-k 位，为了防止符号位影响，我们通常使用无符号类型。
   • x = 1101 (13), n=4, k=1。n-k=3。x >> 3 得到 0001 (1)。

3. 合并两部分：

   • 将上面两步的结果进行按位或 操作，合并成最终结果。
   • 1010 | 0001 = 1011 (11)，这正是我们想要的结果。

完整代码实现

下面是一个完整的 C 语言程序，实现了对 unsigned int 类型的循环左移和循环右移函数。

#include <stdio.h>
// 假设我们操作的是 32 位整数
#define INT_BITS 32
/**
 * @brief 循环左移
 * @param x 要移位的无符号整数
 * @param k 要移动的位数
 * @return 循环左移 k 位后的结果
 */
unsigned int rol(unsigned int x, unsigned int k) {
    // 处理 k 大于 32 的情况，因为循环32位等于没动
    k %= INT_BITS;
    // 分离并合并
    // (x << k) 将高 k 位移到目标位置，低 k 位变为 0
    // (x >> (INT_BITS - k)) 将低 (32-k) 位移到目标位置，高 (32-k) 位变为 0
    // | 操作将两部分合并
    return (x << k) | (x >> (INT_BITS - k));
}
/**
 * @brief 循环右移
 * @param x 要移位的无符号整数
 * @param k 要移动的位数
 * @return 循环右移 k 位后的结果
 */
unsigned int ror(unsigned int x, unsigned int k) {
    // 处理 k 大于 32 的情况
    k %= INT_BITS;
    // 分离并合并
    // (x >> k) 将低 k 位移到目标位置，高 k 位变为 0
    // (x << (INT_BITS - k)) 将高 (32-k) 位移到目标位置，低 (32-k) 位变为 0
    // | 操作将两部分合并
    return (x >> k) | (x << (INT_BITS - k));
}
// 辅助函数：打印一个整数的二进制形式
void print_binary(unsigned int n) {
    for (int i = INT_BITS - 1; i >= 0; i--) {
        printf("%d", (n >> i) & 1);
        if (i % 8 == 0) printf(" "); // 每8位加一个空格，方便阅读
    }
    printf("\n");
}
int main() {
    unsigned int num = 0b11001100110011001100110011001100; // 一个示例数字
    unsigned int k = 4;
    printf("原始数字: \n");
    print_binary(num);
    printf("十进制: %u\n\n", num);
    // --- 循环左移 ---
    unsigned int left_rotated = rol(num, k);
    printf("循环左移 %d 位后: \n", k);
    print_binary(left_rotated);
    printf("十进制: %u\n\n", left_rotated);
    // --- 循环右移 ---
    unsigned int right_rotated = ror(num, k);
    printf("循环右移 %d 位后: \n", k);
    print_binary(right_rotated);
    printf("十进制: %u\n\n", right_rotated);
    // --- 测试循环移动位数超过整数宽度的情况 ---
    unsigned int k2 = 36; // 36 % 32 = 4, 效果应该和移动4位一样
    unsigned int left_rotated_2 = rol(num, k2);
    printf("循环左移 %d 位 (36 %% 32 = 4) 后: \n", k2);
    print_binary(left_rotated_2);
    printf("十进制: %u\n", left_rotated_2);
    return 0;
}

代码解析

1. 使用 unsigned int：这是关键，使用无符号整数可以确保右移操作是逻辑右移（高位补0），而不是算术右移（高位补符号位），这对于循环移位是正确的行为。
2. k %= INT_BITS：这是一个重要的优化，对于一个32位的整数，循环左移32位等于没有移动，这个操作可以确保 k 的值在0到31之间，避免了不必要的计算。
3. << 和 >>：分别是左移和右移位运算符。
4. ：是按位或运算符，当两个操作数中对应位有一个为1时，结果的该位就为1，它完美地将两部分“拼接”在一起。

C11 标准中的循环移位

从 C11 标准开始，C 语言在 <stdatomic.h> 头文件中引入了针对原子类型的循环移位函数，这些函数主要用于多线程编程，以确保操作是原子的（不会被其他线程打断）。

• atomic_fetch_add_explicit (用于原子加)
• atomic_fetch_sub_explicit (用于原子减)
• atomic_flag_test_and_set (用于原子标志)

请注意：C11 并没有为普通整数（如 int）提供通用的 rol/ror 函数，这些原子函数主要用于更底层的并发控制。

在大多数情况下,尤其是在非多线程环境或算法实现中，我们仍然需要手动实现上面介绍的位运算方法。

循环移位的应用

循环移位在许多领域都有重要应用：

1. 密码学：许多加密算法（如 DES、RC5）在内部使用了大量的循环移位操作来打乱数据，增加破解难度。
2. 哈希函数：在计算哈希值时，循环移位可以很好地混合输入数据的各个部分，使哈希结果分布更均匀，减少冲突。
3. 图像处理：在某些图像旋转或像素重排算法中，可能会用到循环移位的思想。
4. 嵌入式系统与驱动开发：在操作硬件寄存器时，有时需要通过移位来配置特定位段。
5. 算法竞赛：这是一个非常经典的位操作题目，经常出现在编程竞赛中，考察选手对二进制和位运算的熟练程度。

掌握循环移位的原理和实现方法是 C 程序员一项非常有用的技能，希望这个详细的解释能帮助你彻底理解它！