一、前言

  本文作者是从 2007 年开始学 C语言 的，不久又接触了C++，基本就是 C/C++ 技术栈写了 14 年的样子，不算精通，但也算差强人意。著有《夜深人静写算法》系列，且承诺会持续更新，直到所有算法都学完。主要专攻 高中 OI 、大学 ACM、 职场 LeetCode 的全领域算法。由于文章中采用 C/C++ 的语法，于是就有不少读者朋友反馈语言层面就被劝退了，更何况是算法。
  于是，2021 年 06 月 12 日，《光天化日学C语言》 应运而生。这个系列文章主要服务于高中生、大学生以及职场上想入坑C语言的志同道合之人，希望能给祖国引入更多编程方面的人才，并且让自己的青春不留遗憾！
  这一章的主要内容是右移运算符的应用。

二、人物简介

• 第一位登场的就是今后会一直教我们C语言的老师 —— 光天。
  
• 第二位登场的则是今后会和大家一起学习C语言的没什么资质的小白程序猿 —— 化日。
  

三、右移运算符

1、右移的二进制形态

• 右移运算符是一个二元的位运算符，也就是有两个操作数，表示为x >> y。其中x和y均为整数。
• x >> y念作：“将 $x$ 右移 $y$ 位”，这里的位当然就是二进制位了，那么它表示的意思也就是：先将 $x$ 用二进制表示，对于正数，右移 $y$ 位；对于负数，右移 $y$ 位后高位都补上 1。
• 举个例子：对于二进制数 $87_{10} = (1010111)_2$ 左移 $y$ 位的结果就是：

$$(1010)_2$$

2、右移的执行结果

• x >> y的执行结果等价于：

• $$\lfloor \frac x {2^y} \rfloor$$

• 其中 $\lfloor a\rfloor$ 代表对 $a$ 取下整。
• 如下代码：

#include <stdio.h>
int main() {
    int x = 0b1010111;
    int y = 3;
    printf("%d\n", x >> y);
    return 0;
}

• 输出结果为：

10

• 正好符合这个右移运算符的实际含义：

• $$10 = \lfloor \frac {87} {2^3} \rfloor$$

由于除法可能造成不能整除，所以才会有 取下整 这一步运算。

3、负数右移的执行结果

• 所谓负数右移，就是x >> y中，当x为负数的情况，代码如下：

#include <stdio.h>
int main() {
    printf("%d\n", -1 >> 1);
    return 0;
}

• 它的输出如下：

-1

• 我们发现同样是满足 $\lfloor \frac x {2^y} \rfloor$ 的（注意，负数的 取下整 和 正数 是正好相反的），这个可以用补码来解释，-1的补码为：

• $$11111111 \ 11111111 \ 11111111 \ 11111111$$

• 右移一位后，由于是负数，高位补上 1，得到：

• $$11111111 \ 11111111 \ 11111111 \ 11111111$$

• 而这，正好是 -1的补码，同样，继续右移 1 位，得到：

可以理解成 - (x >> y)和(-x) >> y是等价的。

【例题1】要求不运行代码，肉眼看出这段代码输出多少。

#include <stdio.h>
int main() {
    int x = (1 << 31) | (1 << 30) | 1;
    int y = (1 << 31) | (1 << 30) | (1 << 29);
    printf("%d\n", (x >> 1) / y);
    return 0;
}

4、右移负数位是什么情况

• 刚才我们讨论了 $x < 0$ 的情况，那么接下来，我们试下 $y < 0$ 的情况会是如何？
• 是否同样满足： $\lfloor \frac x {2^y} \rfloor$ 呢？
• 如果还是满足，那么两个整数的左移就有可能产生小数了。
• 看个例子：

#include <stdio.h>
int main() {
    printf("%d\n", 1 >> -1);   // 2
    printf("%d\n", 1 >> -2);   // 4
    printf("%d\n", 1 >> -3);   // 8
    printf("%d\n", 1 >> -4);   // 16
    printf("%d\n", 1 >> -5);   // 32
    printf("%d\n", 1 >> -6);   // 64
    printf("%d\n", 1 >> -7);   // 128
    return 0;
}

• 虽然能够正常运行，但是结果好像不是我们期望的，而且会报警告如下：

[Warning] right shift count is negative [-Wshift-count-negative]

• 实际上，编辑器告诉我们尽量不用右移的时候用负数，但是它的执行结果不能算错误，起码例子里面对了。
• 右移负数位其实效果和左移对应正数数值位一致。
• 左移相关的内容，可以参考：光天化日学C语言（18）- 位运算 << 的应用。

四、右移运算符的应用

1、去掉低 k 位

【例题2】给定一个数 $x$，去掉它的低 $k$ 位以后进行输出。

• 这个问题，可以直接通过右移来完成，如下：x >> k。

2、取低位连续 1

【例题3】获取一个数 $x$ 低位连续的 1 并且输出。

• 对于一个数 $x$，假设低位有连续 $k$ 个 1。如下：

• $$(...0\underbrace{1...1}_{\rm k})_2$$

• 然后我们将它加上 1 以后，得到的就是：

• $$(...1\underbrace{0...0}_{\rm k})_2$$

• 这时候将这两个数异或结果为：

• $$(\underbrace{1...1}_{\rm {k+1}})_2$$

• 这时候，再进行右移一位，就得到了 连续 $k$ 个 1 的值，也正是我们所求。
• 所以可以用以下语句来求：(x ^ (x + 1)) >> 1。

3、取第k位的值

【例题4】获取一个数 $x$ 的第 $k(0 \le k \le 30)$ 位的值并且输出。

• 对于二进制数来说，第 $k$ 位的值一定是 0 或者 1。
• 而 对于 1 到 $k-1$ 位的数字，对于我们来说是没有意义的，我们可以用右移来去掉，再用位与运算符来获取二进制的最后一位是 0 还是 1，如下：(x >> k) & 1。

通过这一章，我们学会了：
  1）位运算 >> 的用法；
  2）用 >> 来取低位连续 1；
  3）用 >> 取第 $k$ 位的值；

• 希望对你有帮助哦 ~ 祝大家早日成为 C 语言大神！

课后习题

• 【第44题】右移的应用 | (更新中)