妹妹最近要考计算机二级了,选的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,转换成二进制就是101
,101
&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^n
或m/2^n
,大家可以观察二进制转换为十进制的计算方法,很容易就能明白。
尾巴
关于C语言中的位运算符的基础知识暂时就讲到这里,其实位运算符在很多场景下可以帮助我们优化程序的运行效率,比如我们可以使用m >> 1
来代替需要m / 2
的场景,这样可以使得程序的运行效率大大提高,比如二分查找、堆的插入操作等等。欢迎大家在评论区留言哦~
这些基础的说起来简单,就是记不住
还是很有意思的哈哈
东哥优秀ヾ(≧∇≦*)ゝ
晚安