C/C++之逻辑右移与算术右移

设符号数表示为: $x = -u_{n-1}2^{n-1} + \sum_{i=0}^{n-2}{u_i2^{i}}$ , $u_i \in \{0, 1\}$ (采用 two's complement 编码方式).

逻辑右移, 其中 $k \in \{0, 1, \cdots, n-1\}$ :

$$\begin{aligned} x \gg_L k &:= \left\lfloor\left(\sum_{i=0}^{n-1}{u_i2^{i}}\right) / 2^k \right\rfloor = \left\lfloor\sum_{i=0}^{n-1}{u_i2^{i - k}} \right\rfloor \\ &= \sum_{i=k}^{n-1}{u_i2^{i - k}} = \sum_{i=0}^{n-k-1}{u_{i + k}2^{i}} \end{aligned}$$

算术右移, 其中 $k \in \{0, 1, \cdots, n-1\}$ :

$$\begin{aligned} x \gg_A k &:= \left\lfloor x / 2^k \right\rfloor \\ &= \left\lfloor -u_{n-1}2^{n - k - 1} + \sum_{i=0}^{n-2}{u_i2^{i - k}} \right\rfloor \\ &= -u_{n-1}2^{n - k - 1} + \sum_{i=k}^{n-2}{u_i2^{i - k}} \\ &= -u_{n-1}2^{n - k} + \sum_{i=k}^{n-1}{u_i2^{i - k}} \\ &= -u_{n-1}2^{n - k} + \sum_{i=0}^{n-k-1}{u_{i + k}2^{i}} \\ &= u_{n-1} \left(-2^{n- 1} + \sum_{i=n-k}^{n-2}{2^{i}}\right) + \sum_{i=0}^{n-k-1}{u_{i + k}2^{i}} \\ \end{aligned}$$

上面推导借用了结论: $\sum_{i=n}^{m} 2^{i} = 2^{m+1} - 2^{n}$ . 可见算术右移运算对符号位进行了扩展.

所以可得符号数的逻辑右移与算术右移之间的关系, $x \gg_A k = u_{n-1} (-2^{n- 1} + \sum_{i=n-k}^{n-2}{2^{i}}) + x \gg_L k$.

特别地, 当 $x \geq 0$ 时, 即当 $u_{n-1} = 0$ 时, $x \gg_A k = x \gg_L k$ .

在 C++ 14 之前

For unsigned a and for signed and non-negative a , the value of a >> b is the integer part of $a / 2^b$ . For negative a , the value of a >> b is implementation-defined (in most implementations, this performs arithmetic right shift, so that the result remains negative).

在 C++ 14 之后

The value of a >> b is $a / 2^b$ , rounded down (in other words, right shift on signed a is arithmetic right shift).

更新记录

20200722, 发布
20211226, 修改部分内容

C/C++之逻辑右移与算术右移

更新记录

版权声明