☀️光天化日学C语言☀️(19)- 位运算 >> 的应用 | 右移的一些高端用法

举报
英雄哪里出来 发表于 2021/08/08 08:32:04 2021/08/08
【摘要】 右移的一些高端用法

一、前言

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

二、人物简介

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

三、右移运算符

1、右移的二进制形态

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

( 1010 ) 2 (1010)_2

2、右移的执行结果

  • x >> y的执行结果等价于:
  • x 2 y \lfloor \frac x {2^y} \rfloor

  • 其中 a \lfloor a\rfloor 代表对 a a 取下整。
  • 如下代码:
#include <stdio.h>
int main() {
    int x = 0b1010111;
    int y = 3;
    printf("%d\n", x >> y);
    return 0;
}
  • 输出结果为:
10
  • 正好符合这个右移运算符的实际含义:
  • 10 = 87 2 3 10 = \lfloor \frac {87} {2^3} \rfloor

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

3、负数右移的执行结果

  • 所谓负数右移,就是x >> y中,当x为负数的情况,代码如下:
#include <stdio.h>
int main() {
    printf("%d\n", -1 >> 1);
    return 0;
}
  • 它的输出如下:
-1
  • 我们发现同样是满足 x 2 y \lfloor \frac x {2^y} \rfloor 的(注意,负数的 取下整 和 正数 是正好相反的),这个可以用补码来解释,-1的补码为:
  • 11111111   11111111   11111111   11111111 11111111 \ 11111111 \ 11111111 \ 11111111

  • 右移一位后,由于是负数,高位补上 1,得到:
  • 11111111   11111111   11111111   11111111 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 x < 0 的情况,那么接下来,我们试下 y < 0 y < 0 的情况会是如何?
  • 是否同样满足: x 2 y \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 x ,去掉它的低 k k 位以后进行输出。

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

2、取低位连续 1

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

  • 对于一个数 x x ,假设低位有连续 k k 个 1。如下:
  • ( . . . 0 1...1 k ) 2 (...0\underbrace{1...1}_{\rm k})_2

  • 然后我们将它加上 1 以后,得到的就是:
  • ( . . . 1 0...0 k ) 2 (...1\underbrace{0...0}_{\rm k})_2

  • 这时候将这两个数异或结果为:
  • ( 1...1 k + 1 ) 2 (\underbrace{1...1}_{\rm {k+1}})_2

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

3、取第k位的值

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

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

通过这一章,我们学会了:
  1)位运算 >> 的用法;
  2)用 >> 来取低位连续 1;
  3)用 >> 取第 k k 位的值;

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

课后习题


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。