一段代码引发的思考——循环左移

前言

在看源码的时候发现一段代码很神奇，(x << n) | ((x & 0xffffffff) >> (32 - n))。乍一看不知道它在计算啥，又是右移操作，又有左移操作，还涉及到按位与和按位或操作，于是博主就对其做了深入学习。

下文博主会从位运算基础开始，然后深入探讨该表达式的计算过程。

基础——位运算

在深入讨论这段代码之前，先了解一些基本的位运算知识。

• 位移操作（Shift Operations） ：位移操作分为左移（<<）和右移（>>）。左移将二进制数的所有位向左移动指定数量的位数，右移则将所有位向右移动。
  • 例如，x << n 表示将二进制数 x 向左移动 n 位。
• 按位与操作（Bitwise AND） ：按位与操作（&）用于将两个二进制数的对应位进行逻辑与运算。只有当两个操作数的对应位都为 1 时，结果位才为 1，否则为 0。
• 按位或操作（Bitwise OR） ：按位或操作（|）用于将两个二进制数的对应位进行逻辑或运算。只要两个操作数的对应位中至少有一个为 1，结果位就为 1。

循环左移

先解密，这个代码是将一个二进制数循环左移指定位数，并且保持数据的位数不变，即在不改变数据类型或位数的情况下，实现循环移位。

(x << n) | ((x & 0xffffffff) >> (32 - n))

接下来将代码分解来理解：

1. (x << n): 这部分执行标准的左移操作，将整数 x 的所有位向左移动 n 位。这将导致原数的最左边的 n 位移到最右边，并在右侧填充零。
2. x & 0xffffffff: 这部分使用按位与操作，将整数 x 与 32 位的二进制数（0xffffffff）进行逻辑与运算。这实际上将高于 32 位的所有位都设置为零，只保留低 32 位。这是为了确保移动的位数不会受到高位的影响。
3. >> (32 - n): 接下来，对前一步得到的结果进行右移操作，将剩余的 32 位向右移动 (32 - n) 位。这使得之前左移出的位重新出现在最右边。
4. 最后，将两个部分的结果使用按位或操作合并。这会将循环左移后的低位和循环右移后的高位组合起来，得到最终的循环左移结果。

循环左移的计算过程示例

让我们通过一个示例来演示这个表达式的计算过程。假设我们有一个 32 位整数 x，其二进制表示为：

x = 11010110101110100010101011001101

并且我们希望将它循环左移 5 位。现在，让我们按照表达式的步骤来计算：

1. (x << 5)：左移 5 位，得到结果 11010111010001010101100110100000。
2. x & 0xffffffff：按位与操作，结果不变，仍然是 11010110101110100010101011001101。
3. >> (32 - 5)：将上一步结果右移 27 位，得到结果 00000000000000000000000000011010。
4. 最后，将第一步和第三步的结果进行按位或操作：11010111010001010101100110100000 | 00000000000000000000000000011010，得到最终的循环左移结果为 11010111010001010101100110111010。

通过这个计算过程，成功地将整数 x 循环左移了 5 位，同时保持了 32 位的位数不变。