文章目录
一、前言
今天主要内容是聊一聊二进制和位运算。
对应视频教程如下：位运算视频教程。
二、再谈二进制
我们在学习 光天化日学C语言（06）- 进制转换入门 的时候，曾经提到过二进制。
二进制就是逢二进一，计算机中的存储采用的就是二进制。在计算机中，非零即一。
1、二进制数值表示
例如，在计算机中，我们可以用单纯的 0 和 1 来表示数字。
1、101、1100011、100101010101 都是二进制数。
123、423424324、101020102101AF 则不是，因为有 0 和 1 以外的数字位。
一般为了不产生二义性，我们会在数字的右下角写上它的进制，例如：
1010(10)1010_{(10)}1010(10) 代表的是十进制下的 1010，也就是十进制下的 “一千零一十”。1010(2)1010_{(2)}1010(2) 代表的是二进制下的 1010，也就是十进制下的 “十”。
2、二进制加法
二进制加法采用从低到高的位依次相加，当相加的和为2时，则向高位进位。
例如，在二进制中，加法如下：
1(2)+1(2)=10(2)1(2)+0(2)=1(2)0(2)+1(2)=1(2)0(2)+0(2)=0(2)1_{(2)} + 1_{(2)} = 10_{(2)} \\ 1_{(2)} + 0_{(2)} = 1_{(2)} \\ 0_{(2)} + 1_{(2)} = 1_{(2)} \\ 0_{(2)} + 0_{(2)} = 0_{(2)}1(2)+1(2)=10(2)1(2)+0(2)=1(2)0(2)+1(2)=1(2)0(2)+0(2)=0(2)
3、二进制减法
二进制减法采用从低到高的位依次相减，当遇到 0 减 1 的情况，则向高位借位。
例如，在二进制中：减法如下：
1(2)−1(2)=0(2)1(2)−0(2)=1(2)10(2)−1(2)=1(2)0(2)−0(2)=0(2)1_{(2)} - 1_{(2)} = 0_{(2)} \\ 1_{(2)} - 0_{(2)} = 1_{(2)} \\ 10_{(2)} - 1_{(2)} = 1_{(2)} \\ 0_{(2)} - 0_{(2)} = 0_{(2)}1(2)−1(2)=0(2)1(2)−0(2)=1(2)10(2)−1(2)=1(2)0(2)−0(2)=0(2) 而我们今天要讲的位运算正是基于二进制展开的。
三、位运算简介
位运算可以理解成对二进制数字上的每一个位进行操作的运算。位运算分为 逻辑（布尔）位运算符 和 移位位运算符。
逻辑位运算符又分为 位与(&)、位或(|)、异或(^)、按位取反(~)；移位位运算符分为 左移(<<) 和 右移(>>)。
如图所示：
1、位与的定义
位与运算符是一个二元的位运算符，也就是有两个操作数，表示为
x & y
。
位与运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共
22=42^2 = 422=4 种情况。
左操作数右操作数结果000010100111
通过这个表，我们得出一些结论：
1）无论是 0 或 1，只要位与上 1，还是它本身；
2）无论是 0 或 1，只要位与上 0，就变成 0；
#include<stdio.h>intmain(){int a =0b1010;// (1)int b =0b0110;// (2)printf("%d\n",(a & b));// (3)return0;}
( 1 ) (1) (1) 在C语言中，以```0b```作为前缀，表示这是一个二进制数。那么```a```的实际值就是 ( 1010 ) 2 (1010)_2 (1010)2。
( 2 ) (2) (2) 同样的，```b```的实际值就是 ( 0110 ) 2 (0110)_2 (0110)2；
( 3 ) (3) (3) 那么这里```a & b```就是对 ( 1010 ) 2 (1010)_2 (1010)2 和 ( 0110 ) 2 (0110)_2 (0110)2 的每一位做表格中的```&```运算。
所以最后输出结果为：
2
因为输出的是十进制数，它的二进制表示为：
(0010)2(0010)_2(0010)2。注意：这里的 **前导零** 可有可无，作者写上前导零只是为了对齐以及让读者更加清楚位与的运算方式。
2、位与运算符的简单应用
1）奇偶性判定
我们判断一个数是奇数还是偶数，往往是通过取模
%
来判断的，如下：
#include<stdio.h>intmain(){if(5%2==1){printf("5是奇数\n");}if(6%2==0){printf("6是偶数\n");}return0;}
然而，我们也可以这么写：
#include<stdio.h>intmain(){if(5&1){printf("5是奇数\n");}if((6&1)==0){printf("6是偶数\n");}return0;}
这是利用了奇数和偶数分别的二进制数的特性，如下表所示：
-二进制末尾位奇数1偶数0
所以，我们对任何一个数，通过将它和
0b1
进行位与，结果为零，则必然这个数的二进制末尾位为0，根据以上表就能得出它是偶数了；否则，就是奇数。
2）取末五位
给定一个数，求它的二进制表示的末五位，以十进制输出即可。
这个问题的核心就是：我们只需要末五位，剩下的位我们是不需要的，所以可以将给定的数 位与上
0b11111
，这样一来就直接得到末五位的值了。代码实现如下：
#include<stdio.h>intmain(){int x;scanf("%d",&x);printf("%d\n",(x &0b11111));return0;}
3）消除末尾五位
给定一个 32 位整数，要求消除它的末五位。
还是根据位与的性质，消除末五位的含义，有两层：
1）末五位，要全变成零；
2）剩下的位不变；
那么，根据位运算的性质，我们需要数，它的高27位都为1，低五位都为 0，则这个数就是：
(11111111111111111111111111100000)2(11111111111111111111111111100000)_2(11111111111111111111111111100000)2 但是如果要这么写，代码不疯掉，人也会疯掉，所以一般我们把它转成十六进制，每四个二进制位可以转成一个十六进制数，所以得到十六进制数为
0xffffffe0
。代码实现如下：
#include<stdio.h>intmain(){int x;scanf("%d",&x);printf("%d\n",(x &0xffffffe0));return0;}
4）2的幂判定
请用一句话，判断一个正数是不是2的幂。
如果一个数是 2 的幂，它的二进制表示必然为以下形式：
100...00⏟k1\underbrace{00...00}_{\rm k}1k00...00 这个数的十进制值为2k2^k2k。那么我们将它减一，即2k−12^k-12k−1 的二进制表示如下（参考二进制减法的借位）：011...11⏟k0\underbrace{11...11}_{\rm k}0k11...11于是 这两个数位与的结果为零，于是我们就知道了如果一个数xxx 是 2 的幂，那么
x & (x-1)
必然为零。而其他情况则不然。
所以本题的答案为：
(x &(x-1))==0
3、位或的定义
位或运算符是一个二元的位运算符，也就是有两个操作数，表示为
x | y
。
位或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共
22=42^2 = 422=4 种情况。
左操作数右操作数结果000011101111
通过这个表，我们得出一些结论：
1）无论是 0 或 1，只要位或上 1，就变成1；
2）只有当两个操作数都是0的时候，才变成 0；
#include<stdio.h>intmain(){int a =0b1010;// (1)int b =0b0110;// (2)printf("%d\n",(a | b));// (3)return0;}
( 1 ) (1) (1) 在C语言中，以```0b```作为前缀，表示这是一个二进制数。那么```a```的实际值就是 ( 1010 ) 2 (1010)_2 (1010)2。
( 2 ) (2) (2) 同样的，```b```的实际值就是 ( 0110 ) 2 (0110)_2 (0110)2；
( 3 ) (3) (3) 那么这里```a | b```就是对 ( 1010 ) 2 (1010)_2 (1010)2 和 ( 0110 ) 2 (0110)_2 (0110)2 的每一位做表格中的```|```运算。
所以最后输出结果为：
14
因为输出的是十进制数，它的二进制表示为：
(1110)2(1110)_2(1110)2。
4、位或运算符的简单应用
1）设置标记位
【例题1】给定一个数，判断它二进制低位的第 5 位，如果为 0，则将它置为 1。
这个问题，我们很容易联想到位或。
我们分析一下题目意思，如果第 5 位为 1，不用进行任何操作；如果第 5 位为 0，则置为 1。言下之意，无论第五位是什么，我们都直接置为 1即可，代码如下：
#include<stdio.h>intmain(){int x;scanf("%d",&x);printf("%d\n", x |0b10000);return0;}
2）置空标记位
【例题2】给定一个数，判断它二进制低位的第 5 位，如果为 1，则将它置为 0。
这个问题，我们在学过 《算法零基础100讲》(第42讲) 位运算 (位与) 入门 以后，很容易得出这样一种做法：
#include<stdio.h>intmain(){int x;scanf("%d",&x);printf("%d\n", x &0b11111111111111111111111111101111);return0;}
其它位不能变，所以位与上1；第5位要置零，所以位与上0；
这样写有个问题，就是这串数字太长了，一点都不美观，而且容易写错，当然我们也可以转换成 十六进制，转换的过程也有可能出错。
而我们利用位或，只能将第5位设置成1，怎么把它设置成0呢？
我们可以配合减法来用。分成以下两步：
1）首先，强行将低位的第5位置成1；
2）然后，强行将低位的第5位去掉；
第
(1)(1)(1) 步可以采用位或运算，而第(2)(2)(2) 步，我们可以直接用减法即可。代码实现如下：
#include<stdio.h>intmain(){int x;int a =0b10000;scanf("%d",&x);printf("%d\n",(x | a)- a );return0;}
注意：直接减是不行的，因为我们首先要保证那一位为 1，否则贸然减会产生借位，和题意不符。
5、异或运算符的定义
异或运算符是一个二元的位运算符，也就是有两个操作数，表示为
x ^ y
。
异或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共
22=42^2 = 422=4 种情况。
左操作数右操作数结果000011101110
通过这个表，我们得出一些结论：
1）两个相同的十进制数异或的结果一定为零。
2）任何一个数和 0 的异或结果一定是它本身。
3）异或运算满足结合律和交换律。
#include<stdio.h>intmain(){int a =0b1010;// (1)int b =0b0110;// (2)printf("%d\n",(a ^ b));// (3)return0;}
( 1 ) (1) (1) 在C语言中，以```0b```作为前缀，表示这是一个二进制数。那么```a```的实际值就是 ( 1010 ) 2 (1010)_2 (1010)2。
( 2 ) (2) (2) 同样的，```b```的实际值就是 ( 0110 ) 2 (0110)_2 (0110)2；
( 3 ) (3) (3) 那么这里```a ^ b```就是对 ( 1010 ) 2 (1010)_2 (1010)2 和 ( 0110 ) 2 (0110)_2 (0110)2 的每一位做表格中的```^```运算。
所以最后输出结果为：
12
。因为输出的是十进制数，它的二进制表示为：
(1100)2(1100)_2(1100)2。
6、异或运算符的应用
1）标记位取反
【例题1】给定一个数，将它的低位数起的第 4 位取反，0 变 1，1 变 0。
这个问题，我们很容易联想到异或。我们分析一下题目意思，如果第 4 位为 1，则让它异或上
0b1000
就能变成 0；如果第 4 位 为 0，则让它异或上
0b1000
就能变成 1，也就是无论如何都是异或上
0b1000
，代码如下：
#include<stdio.h>intmain(){int x;scanf("%d",&x);printf("%d\n", x ^0b1000);return0;}
2）变量交换
【例题2】给定两个数
aaa 和bbb，用异或运算交换它们的值。
这个是比较老的面试题了，直接给出代码：
#include<stdio.h>intmain(){int a, b;while(scanf("%d %d",&a,&b)!=EOF){a = a ^ b;// (1)b = a ^ b;// (2)a = a ^ b;// (3)printf("%d %d\n", a, b);}return0;}
我们直接来看
(1)(1)(1) 和(2)(2)(2) 这两句话，相当于
b
等于
a ^ b ^ b
，根据异或的几个性质，我们知道，这时候的
b
的值已经变成原先
a
的值了。
而再来看第
(3)(3)(3) 句话，相当于
a
等于
a ^ b ^ a
，还是根据异或的几个性质，这时候，
a
的值已经变成了原先
b
的值。
从而实现了变量
a
和
b
的交换。
3）出现奇数次的数
【例题3】输入
nnn 个数，其中只有一个数出现了奇数次，其它所有数都出现了偶数次。求这个出现了奇数次的数。
根据异或的性质，两个一样的数异或结果为零。也就是所有出现偶数次的数异或都为零，那么把这
nnn 个数都异或一下，得到的数就一定是一个出现奇数次的数了。
#include<stdio.h>intmain(){int n, x, i, ans;scanf("%d",&n);ans =0;for(i =0; i < n;++i){scanf("%d",&x);ans =(ans ^ x);}printf("%d\n", ans);return0;}
光天化日学C语言（14）- 位运算 & 的应用
光天化日学C语言（15）- 位运算 | 的应用
光天化日学C语言（16）- 位运算 ^ 的应用
光天化日学C语言（17）- 位运算 ~ 的应用
光天化日学C语言（18）- 位运算 << 的应用**
**光天化日学C语言（19）- 位运算 >> 的应用
四、位运算概览
今天，我们先来对位运算进行一个初步的介绍。后面会对每个运算符的应用做详细介绍，包括刷题的时候如何运用位运算来加速等等。
1、逻辑位运算
对于布尔位运算，总共有四个，如下表所示：
C语言运算符表示含义示例
&
位与
x & y
|
位或
x | y
^
异或
x ^ y
~
按位取反
x ~ y
1）位与
位与就是对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共
22=42^2 = 422=4 种情况。
左操作数右操作数结果000010100111
#include<stdio.h>intmain(){int a =0b1010;// (1)int b =0b0110;// (2)printf("%d\n",(a & b));// (3)return0;}
( 1 ) (1) (1) 在C语言中，以```0b```作为前缀，表示这是一个二进制数。那么```a```的实际值就是 ( 1010 ) 2 (1010)_2 (1010)2。
( 2 ) (2) (2) 同样的，```b```的实际值就是 ( 0110 ) 2 (0110)_2 (0110)2；
( 3 ) (3) (3) 那么这里```a & b```就是对 ( 1010 ) 2 (1010)_2 (1010)2 和 ( 0110 ) 2 (0110)_2 (0110)2 的每一位做表格中的```&```运算。
- 所以最后输出结果为：
2
因为输出的是十进制数，它的二进制表示为：
(0010)2(0010)_2(0010)2。
注意：这里的 前导零 可有可无，作者写上前导零只是为了对齐以及让读者更加清楚位与的运算方式。
2）位或
位或的运算结果如下：
左操作数右操作数结果000011101111
我们来看以下这段程序：
#include<stdio.h>intmain(){int a =0b1010;int b =0b0110;printf("%d\n",(a | b));return0;}
以上程序的输出结果为：
14
即二进制下的
(1110)2(1110)_2(1110)2 。
3）异或
异或的运算结果如下：
左操作数右操作数结果000011101110
我们来看以下这段程序：
#include<stdio.h>intmain(){int a =0b1010;int b =0b0110;printf("%d\n",(a ^ b));return0;}
以上程序的输出结果为：
12
即二进制下的
(1100)2(1100)_2(1100)2 。
4）按位取反
按位取反其实就是 0 变 1， 1 变 0。
同样，我们来看一段程序。
#include<stdio.h>intmain(){int a =0b1;printf("%d\n",~a );return0;}
这里我想卖个关子，同学们可以自己试一下运行结果。
至于为什么会输出这个结果，我会在 光天化日学C语言（17）- 位运算 ~ 的应用 中进行详细讲解。
2、移位位运算
对于移位位运算，总共有两个，如下表所示：
C语言运算符表示含义示例
<<
左移
x << y
>>
右移
x >> y
1）左移
其中
x << y
代表将二进制的
xxx 的末尾添加yyy 个零，就好比向左移动了yyy 位。
比如
(1011)2(1011)_2(1011)2 左移三位的结果为：(1011000)2(1011000)_2(1011000)2。
2）右移
其中
x >> y
代表将二进制的
xxx 从右边开始截掉yyy 个数，就好比向右移动了yyy 位。
比如
(101111)2(101111)_2(101111)2 右移三位的结果为：(101)2(101)_2(101)2。
版权归原作者 英雄哪里出来 所有， 如有侵权，请联系我们删除。