Okay, three, two, one, let's jam

222 移位运算

5 min read

移位运算

230 逻辑移位和算数移位

逻辑移位

  • 定义与特点：适用于无符号数，或将带符号数视为无符号数进行移位。移位过程中，空出的位补 0。
  • 逻辑左移 (LSL)：
    • 所有位向左移动指定位数。
    • 最高位（MSB）移出，最低位（LSB）补 0。
    • 效果：相当于原数乘以 2^k (k 为移位位数)，但可能发生溢出（数值超过表示范围）。
  • 逻辑右移 (LSR)：
    • 所有位向右移动指定位数。
    • 最低位（LSB）移出，最高位（MSB）补 0。
    • 效果：相当于原数除以 2^k (k 为移位位数)，并向下取整（对于正数）。

算数移位

  • 定义与特点：主要用于带符号数（通常采用补码表示），移位过程中需保持符号位不变或根据规则补位，以保持数值的符号和相对大小关系。
  • 算数左移 (ASL)：
    • 所有位（含符号位）左移，低位补 0
    • 最高数值位移出（可能影响溢出标志）
    • 效果：相当于原数乘以
    • 当移出的最高数值位 ≠ 新的符号位时发生溢出
  • 算数右移 (ASR)：
    • 符号位不变，数值位向右移。
    • 最高位（MSB）补符号位（即，正数补 0，负数补 1）。最低位（LSB）移出。
    • 效果：相当于原数除以 2^k。对于正数，相当于向下取整；对于负数，相当于向负无穷方向取整，保持符号。

C 语言中的左移和右移

循环移位

  • 定义与特点：移出的位会重新回到另一端空出的位置，形成循环。通常用于数据加密、校验和位操作。
  • 不带进位位的循环移位（小循环）：
    • 循环左移 (ROL 或 RL)：最高位（MSB）移出，并进入最低位（LSB）。
    • 循环右移 (ROR 或 RR)：最低位（LSB）移出，并进入最高位（MSB）。
    • 同时，移出的最高位/最低位也会被复制到进位标志位（CF）。
  • 带进位位的循环移位 (CARRY)（大循环）：
    • 循环带进位左移 (RCL)：最高位（MSB）移出并进入进位标志位 C，原进位标志位 C 进入最低位（LSB）。
    • 循环带进位右移 (RCR)：最低位（LSB）移出并进入进位标志位 C，原进位标志位 C 进入最高位（MSB）。
    • 作用：常用于处理超过一个字长的数据的移位（如双字长数的移位），或在某些算法中利用进位位作为临时存储。

循环移位的应用主要有加密算法、哈希函数、优化算法

循环移位的 C 语言实现

循环移位在 C 语言中通常通过结合位左移 (<<)、位右移 (>>) 和位或 (|) 操作来实现。其基本思想是将要移出的位通过一次移位操作“推出”，然后将这些“推出”的位通过另一次移位操作“送回”到另一端，最后通过位或操作将两部分结果合并。

#include <stdio.h>
 
/* 循环左移 */
unsigned int circularLeftShift(unsigned int value, int n) {
    return (value << n) | (value >> (32 - n));
}
 
/* 循环右移 */
unsigned int circularRightShift(unsigned int value, int n) {
    return (value >> n) | (value << (32 - n));
}
 
int main() {
    unsigned int usi = 0x12345678; // 待循环移位的32位无符号整数
    int d = 4;                     // 移位距离（即一次循环移动几位）
    
    printf("Original value: 0x%x\n", usi);
    printf("Circular left shift by %d bits: 0x%x\n", d, circularLeftShift(usi, d));
    printf("Circular right shift by %d bits: 0x%x\n", d, circularRightShift(usi, d));
    
    return 0;
}

Graph View

Backlinks