maxoyed

C语言中的位运算
妹妹最近要考计算机二级了,选的C,今天问到我关于位运算的问题,给她解答完之后,发现位运算其实有很多可玩的地方,故把...
扫描右侧二维码阅读全文
13
2018/09

C语言中的位运算

妹妹最近要考计算机二级了,选的C,今天问到我关于位运算的问题,给她解答完之后,发现位运算其实有很多可玩的地方,故把C语言中位运算的基础知识整理成此文。

一、运算符

运算符定义
&“与”,除了1 & 1 = 1,其余均为0
| “或”,除了0 | 0 = 0,其余均为1
“非”,取反,^ 1 = 0,^ 0 = 1
^“异或”,若异或的两数不同则结果为1,否则为0。(同0异1)
<<“左移”,将二进制数向左移n位,后面用0补全。如:1001 << 2 = 100100
>>“右移”,将二进制数向右移n位,也可以理解为删除后面的n位。如:1001 >> 2 = 10

二、位运算的实际运用

1. & 运算

&运算可以用来判断数的奇偶。比如,十进制的4,转换成二进制就是100,这时,我们可以用100 & 1,即100 & 001,结果为0(二进制的运算是从左到右,逐位运算,右边对齐,空位补零),可知该数为偶数;十进制的5,转换成二进制就是101101 &001=1,可知该数为奇数。

PS:这是因为二进制转换为十进制时,是每一位的数(0或1)乘以2的n-1次方(n为该数所在的位数,如二进制数100转换为十进制:

1*2^2 + 0*2^1 + 0*2^0 = 4 +0 +0 = 4。当二进制数100和1进行&运算时,由于1(001)前面都为0,所以结果只和最后一位有关系,最后一位为0,则&1结果为0,反之则为1。从上面二进制转十进制的过程可以看到,前面都是2*n相加,为偶数,最后一位是n*2^0=n,所以结果是奇是偶只和最后一位是1还是0有关。)

2. | 运算

|运算可以用来把一个二进制数的最后一位变成1。比如,十进制数5,转换为二进制就是101,这时,我们可以用101 | 1(即101 | 001),按照二进制位运算的规则:从左到右,逐位运算,右边对齐,空位补零,这个式子的结果应该为101,最后一位为1;同理,十进制数4,转换为二进制就是100,100 | 1(即100 | 001)的结果为101,最后一位同样为1。

PS:我们可以利用这个方法取到不大于某数的最大偶数。假设有数N,( N | 1 ) - 1的结果就是不大于N的最大偶数,例如有十进制数5,则( 5 | 1 ) - 1 = 4( (101|001) - 1 = 100 )。

3. ~ 运算

`~` 运算比较简单,对二进制数逐位取反就可以了,如十进制数4(`100`),对其进行`~`运算,即~4

( ~ 100 ),结果为011,即十进制数3。

4. ^ 运算

^运算可以用来交换两个变量的数和进行简单的数据加密。

^运算有一个特点,即^运算的逆运算是^本身。举个例子,我们把十进制数4(100)和十进制数5(101)进行^运算,即4 ^ 5( 100 ^ 101 = 001 ),结果为十进制数1;我们再把十进制数4(100)和十进制数1(001)进行^运算,即4 ^ 1( 100 ^ 001 = 101 ),结果为十进制数5。从这个例子我们就可以验证^运算的逆运算是^本身这一特点。

​ 根据^的逆运算是其本身这一特性,我们可以进行交换变量数据的操作,先贴代码:

#include <stdio.h>

//利用^运算交换两个变量
int main(){
    int a = 4;
    int b = 5;
    printf("Before exchange: a = %d, b = %d.\n", a, b);
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    printf("After exchange:  a = %d, b = %d.\n", a, b);
    return 0;
}

​ 程序运行结果为:

Before exchange: a = 4, b = 5.
After exchange:  a = 5, b = 4.

​ 假设你要把你的手机号在群里告诉你的小伙伴,同时不想让别人知道,那么你可以把你的手机号码和某个你俩都知道的数进行^操作(比如你的生日blablabla),你的小伙伴在收到你的信息后,可以用收到的数和你的生日进行^操作,最终结果就是你的手机号码。

5. << 运算

<<运算可以将m向左移动n位(后面补0)。请大家思考,如果我们计算5 << 4这个表达式,它的结果会如何呢?根据<<运算的定义,将5(101)像左移动4位并在末尾补0,其结果为1010000,即十进制数80,80其实就是5 * ( 2 ^ 4 )的计算结果,大家还可以自己找几个数来试试。不难看出,m << n的结果即为m*2^n,代码如下:

#include <stdio.h>
#include <math.h>

//比较5*2^4和5<<4的计算结果
int main(){
    int shl_result = 5 << 4;
    double pow_result = 5 * pow(2, 4);
    printf("5 * 2 ^ 4 = %lf\n", pow_result);
    printf("5 << 4 = %d\n", shl_result);
    return 0;
}

​ 程序运行结果为:

5 * 2 ^ 4 = 80.000000
5 << 4 = 80

6. >> 运算

>>运算可以将m向右移动n位(后n位直接去掉)。类似<<运算,请大家思考,160 >> 4的结果是多少呢?根据>>运算的定义,将160(10100000)向右移动4位(去掉末尾4个0),其结果为1010,即十进制数10,10其实就是160 / (2 ^ 4)的结果,大家也可以另外找几个数来验证。通过观察不难看出,m >> n的结果即为m /2^n ,代码如下:

#include <stdio.h>
#include <math.h>

//比较160/2^4和160>>4的计算结果
int main(){
    int shr_result = 160 >> 4;
    double pow_result = 160 / pow(2, 4);
    printf("160 / 2 ^ 4 = %lf\n", pow_result);
    printf("160 << 4 = %d\n", shr_result);
    return 0;
}

​ 程序运行结果为:

160 / 2 ^ 4 = 10.000000
160 << 4 = 10

PS:关于<<>>两种移位运算为什么会导致结果等于m*2^nm/2^n,大家可以观察二进制转换为十进制的计算方法,很容易就能明白。

尾巴

​ 关于C语言中的位运算符的基础知识暂时就讲到这里,其实位运算符在很多场景下可以帮助我们优化程序的运行效率,比如我们可以使用m >> 1来代替需要m / 2的场景,这样可以使得程序的运行效率大大提高,比如二分查找、堆的插入操作等等。欢迎大家在评论区留言哦~

Last modification:October 6th, 2018 at 02:05 am
If you think my article is useful to you, please feel free to appreciate

4 comments

  1. 过滤沙缸

    这些基础的说起来简单,就是记不住

  2. 北极以北

    东哥优秀ヾ(≧∇≦*)ゝ

    1. maxoyed
  3. maxoyed

    晚安

Leave a Comment