文章目录

• 一、前言
• 二、再谈二进制
• 1、二进制数值表示
• 2、二进制加法
• 3、二进制减法
• 三、位运算简介
• 1、位与的定义
• 2、位与运算符的简单应用
• 1）奇偶性判定
• 2）取末五位
• 3）消除末尾五位
• 4）2的幂判定
• 3、位或的定义
• 4、位或运算符的简单应用
• 1）设置标记位
• 2）置空标记位
• 5、异或运算符的定义
• 6、异或运算符的应用
• 1）标记位取反
• 2）变量交换
• 3）出现奇数次的数
• 四、位运算概览
• 1、逻辑位运算
• 1）位与
• 2）位或
• 3）异或
• 4）按位取反
• 2、移位位运算
• 1）左移
• 2）右移

一、前言

  今天主要内容是聊一聊二进制和位运算。   对应视频教程如下：位运算视频教程。

二、再谈二进制

我们在学习 光天化日学C语言（06）- 进制转换入门 的时候，曾经提到过二进制。

二进制就是逢二进一，计算机中的存储采用的就是二进制。在计算机中，非零即一。

1、二进制数值表示

例如，在计算机中，我们可以用单纯的 0 和 1 来表示数字。

1、101、1100011、100101010101 都是二进制数。 123、423424324、101020102101AF 则不是，因为有 0 和 1 以外的数字位。

一般为了不产生二义性，我们会在数字的右下角写上它的进制，例如：

101 0 ( 10 ) 1010_{(10)}

1

0

1

0

(

1

0

)

​

代表的是十进制下的 1010，也就是十进制下的 “一千零一十”。

101 0 ( 2 ) 1010_{(2)}

1

0

1

0

(

2

)

​

代表的是二进制下的 1010，也就是十进制下的 “十”。

2、二进制加法

  二进制加法采用从低到高的位依次相加，当相加的和为2时，则向高位进位。

例如，在二进制中，加法如下：

1 ( 2 ) + 1 ( 2 ) = 1 0 ( 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

)

​

=

1

0

(

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 ) 1 0 ( 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

)

​

1

0

(

2

)

​

−

1

(

2

)

​

=

1

(

2

)

​

0

(

2

)

​

−

0

(

2

)

​

=

0

(

2

)

​

而我们今天要讲的位运算正是基于二进制展开的。

三、位运算简介

位运算可以理解成对二进制数字上的每一个位进行操作的运算。位运算分为 逻辑（布尔）位运算符 和 移位位运算符。

逻辑位运算符又分为 位与(&)、位或(|)、异或(^)、按位取反(~)；移位位运算符分为 左移(<<) 和 右移(>>)。如图所示：

1、位与的定义

位与运算符是一个二元的位运算符，也就是有两个操作数，表示为x & y。

位与运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共

2 2 = 4 2^2 = 4

2

2

=

4

种情况。

左操作数	右操作数	结果
0	0	0
0	1	0
1	0	0
1	1	1

通过这个表，我们得出一些结论：

1）无论是 0 或 1，只要位与上 1，还是它本身；2）无论是 0 或 1，只要位与上 0，就变成 0；

#include <stdio.h>
int main() {
    int a = 0b1010;           // (1)
    int b = 0b0110;           // (2)
    printf("%d\n", (a & b) ); // (3)
    return 0;
}

• ( 1 ) (1)

(

1

) 在C语言中，以0b作为前缀，表示这是一个二进制数。那么a的实际值就是

( 1010 ) 2 (1010)_2

(

1

0

1

0

)

2

​

。

• ( 2 ) (2)

(

2

) 同样的，b的实际值就是

( 0110 ) 2 (0110)_2

(

0

1

1

0

)

2

​

；

• ( 3 ) (3)

(

3

) 那么这里a & b就是对

( 1010 ) 2 (1010)_2

(

1

0

1

0

)

2

​

和

( 0110 ) 2 (0110)_2

(

0

1

1

0

)

2

​

的每一位做表格中的&运算。

所以最后输出结果为：2

因为输出的是十进制数，它的二进制表示为：

( 0010 ) 2 (0010)_2

(

0

0

1

0

)

2

​

。注意：这里的 前导零 可有可无，作者写上前导零只是为了对齐以及让读者更加清楚位与的运算方式。

2、位与运算符的简单应用

1）奇偶性判定

我们判断一个数是奇数还是偶数，往往是通过取模%来判断的，如下：

#include <stdio.h>
int main() {
    if(5 % 2 == 1) {
        printf("5是奇数\n");
    }
    if(6 % 2 == 0) {
        printf("6是偶数\n");
    }
    return 0;
}

然而，我们也可以这么写：

#include <stdio.h>
int main() {
    if(5 & 1) {
        printf("5是奇数\n");
    }
    if( (6 & 1) == 0 ) {
        printf("6是偶数\n");
    }
    return 0;
}

这是利用了奇数和偶数分别的二进制数的特性，如下表所示：

-	二进制末尾位
奇数	1
偶数	0

所以，我们对任何一个数，通过将它和 0b1进行位与，结果为零，则必然这个数的二进制末尾位为0，根据以上表就能得出它是偶数了；否则，就是奇数。

2）取末五位

给定一个数，求它的二进制表示的末五位，以十进制输出即可。

这个问题的核心就是：我们只需要末五位，剩下的位我们是不需要的，所以可以将给定的数 位与上0b11111，这样一来就直接得到末五位的值了。代码实现如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", (x & 0b11111) );
    return 0;
}

3）消除末尾五位

给定一个 32 位整数，要求消除它的末五位。

还是根据位与的性质，消除末五位的含义，有两层：

1）末五位，要全变成零；2）剩下的位不变；那么，根据位运算的性质，我们需要数，它的高27位都为1，低五位都为 0，则这个数就是：

( 11111111111111111111111111100000 ) 2 (11111111111111111111111111100000)_2

(

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

)

2

​

但是如果要这么写，代码不疯掉，人也会疯掉，所以一般我们把它转成十六进制，每四个二进制位可以转成一个十六进制数，所以得到十六进制数为0xffffffe0。代码实现如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", (x & 0xffffffe0) );
    return 0;
}

4）2的幂判定

请用一句话，判断一个正数是不是2的幂。

如果一个数是 2 的幂，它的二进制表示必然为以下形式：

1 00...00 ⏟ k 1\underbrace{00...00}_{\rm k}

1

k

0

0

.

.

.

0

0

​

​

这个数的十进制值为

2 k 2^k

2

k

。那么我们将它减一，即

2 k − 1 2^k-1

2

k

−

1

的二进制表示如下（参考二进制减法的借位）：

0 11...11 ⏟ k 0\underbrace{11...11}_{\rm k}

0

k

1

1

.

.

.

1

1

​

​

于是 这两个数位与的结果为零，于是我们就知道了如果一个数

x x

x

是 2 的幂，那么x & (x-1)必然为零。而其他情况则不然。所以本题的答案为：

(x & (x-1)) == 0

3、位或的定义

位或运算符是一个二元的位运算符，也就是有两个操作数，表示为x | y。

位或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共

2 2 = 4 2^2 = 4

2

2

=

4

种情况。

左操作数	右操作数	结果
0	0	0
0	1	1
1	0	1
1	1	1

通过这个表，我们得出一些结论：

1）无论是 0 或 1，只要位或上 1，就变成1；2）只有当两个操作数都是0的时候，才变成 0；

#include <stdio.h>
int main() {
    int a = 0b1010;           // (1)
    int b = 0b0110;           // (2)
    printf("%d\n", (a | b) ); // (3)
    return 0;
}

• ( 1 ) (1)

(

1

) 在C语言中，以0b作为前缀，表示这是一个二进制数。那么a的实际值就是

( 1010 ) 2 (1010)_2

(

1

0

1

0

)

2

​

。

• ( 2 ) (2)

(

2

) 同样的，b的实际值就是

( 0110 ) 2 (0110)_2

(

0

1

1

0

)

2

​

；

• ( 3 ) (3)

(

3

) 那么这里a | b就是对

( 1010 ) 2 (1010)_2

(

1

0

1

0

)

2

​

和

( 0110 ) 2 (0110)_2

(

0

1

1

0

)

2

​

的每一位做表格中的|运算。

所以最后输出结果为：14

因为输出的是十进制数，它的二进制表示为：

( 1110 ) 2 (1110)_2

(

1

1

1

0

)

2

​

。

4、位或运算符的简单应用

1）设置标记位

【例题1】给定一个数，判断它二进制低位的第 5 位，如果为 0，则将它置为 1。

这个问题，我们很容易联想到位或。

我们分析一下题目意思，如果第 5 位为 1，不用进行任何操作；如果第 5 位为 0，则置为 1。言下之意，无论第五位是什么，我们都直接置为 1即可，代码如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x | 0b10000); 
    return 0;
}

2）置空标记位

【例题2】给定一个数，判断它二进制低位的第 5 位，如果为 1，则将它置为 0。

这个问题，我们在学过 《算法零基础100讲》(第42讲) 位运算 (位与) 入门 以后，很容易得出这样一种做法：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x & 0b11111111111111111111111111101111); 
    return 0;
}

其它位不能变，所以位与上1；第5位要置零，所以位与上0；

这样写有个问题，就是这串数字太长了，一点都不美观，而且容易写错，当然我们也可以转换成 十六进制，转换的过程也有可能出错。而我们利用位或，只能将第5位设置成1，怎么把它设置成0呢？

我们可以配合减法来用。分成以下两步：   1）首先，强行将低位的第5位置成1；   2）然后，强行将低位的第5位去掉；

第

( 1 ) (1)

(

1

)步可以采用位或运算，而第

( 2 ) (2)

(

2

)步，我们可以直接用减法即可。代码实现如下：

#include <stdio.h>
int main() {
    int x;
    int a = 0b10000; 
    scanf("%d", &x);
    printf("%d\n", (x | a) - a ); 
    return 0;
}

注意：直接减是不行的，因为我们首先要保证那一位为 1，否则贸然减会产生借位，和题意不符。

5、异或运算符的定义

异或运算符是一个二元的位运算符，也就是有两个操作数，表示为x ^ y。

异或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共

2 2 = 4 2^2 = 4

2

2

=

4

种情况。

左操作数	右操作数	结果
0	0	0
0	1	1
1	0	1
1	1	0

通过这个表，我们得出一些结论：

1）两个相同的十进制数异或的结果一定为零。2）任何一个数和 0 的异或结果一定是它本身。3）异或运算满足结合律和交换律。

#include <stdio.h>
int main() {
    int a = 0b1010;           // (1)
    int b = 0b0110;           // (2)
    printf("%d\n", (a ^ b) ); // (3)
    return 0;
}

• ( 1 ) (1)

(

1

) 在C语言中，以0b作为前缀，表示这是一个二进制数。那么a的实际值就是

( 1010 ) 2 (1010)_2

(

1

0

1

0

)

2

​

。

• ( 2 ) (2)

(

2

) 同样的，b的实际值就是

( 0110 ) 2 (0110)_2

(

0

1

1

0

)

2

​

；

• ( 3 ) (3)

(

3

) 那么这里a ^ b就是对

( 1010 ) 2 (1010)_2

(

1

0

1

0

)

2

​

和

( 0110 ) 2 (0110)_2

(

0

1

1

0

)

2

​

的每一位做表格中的^运算。

所以最后输出结果为：12。因为输出的是十进制数，它的二进制表示为：

( 1100 ) 2 (1100)_2

(

1

1

0

0

)

2

​

。

6、异或运算符的应用

1）标记位取反

【例题1】给定一个数，将它的低位数起的第 4 位取反，0 变 1，1 变 0。

这个问题，我们很容易联想到异或。我们分析一下题目意思，如果第 4 位为 1，则让它异或上 0b1000就能变成 0；如果第 4 位 为 0，则让它异或上 0b1000就能变成 1，也就是无论如何都是异或上 0b1000，代码如下：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x ^ 0b1000); 
    return 0;
}

2）变量交换

【例题2】给定两个数 a a a 和 b b b，用异或运算交换它们的值。

这个是比较老的面试题了，直接给出代码：

#include <stdio.h>
int main() {
    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);
    }
    return 0;
}

我们直接来看

( 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】输入 n n n 个数，其中只有一个数出现了奇数次，其它所有数都出现了偶数次。求这个出现了奇数次的数。

根据异或的性质，两个一样的数异或结果为零。也就是所有出现偶数次的数异或都为零，那么把这

n n

n

个数都异或一下，得到的数就一定是一个出现奇数次的数了。

#include <stdio.h>
int main() {
    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);
    return 0;
}

光天化日学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 两种情况，所以组合出来总共

2 2 = 4 2^2 = 4

2

2

=

4

种情况。

左操作数	右操作数	结果
0	0	0
0	1	0
1	0	0
1	1	1

#include <stdio.h>
int main() {
    int a = 0b1010;           // (1)
    int b = 0b0110;           // (2)
    printf("%d\n", (a & b) ); // (3)
    return 0;
}

• ( 1 ) (1)

(

1

) 在C语言中，以0b作为前缀，表示这是一个二进制数。那么a的实际值就是

( 1010 ) 2 (1010)_2

(

1

0

1

0

)

2

​

。

• ( 2 ) (2)

(

2

) 同样的，b的实际值就是

( 0110 ) 2 (0110)_2

(

0

1

1

0

)

2

​

；

• ( 3 ) (3)

(

3

) 那么这里a & b就是对

( 1010 ) 2 (1010)_2

(

1

0

1

0

)

2

​

和

( 0110 ) 2 (0110)_2

(

0

1

1

0

)

2

​

的每一位做表格中的&运算。

• 所以最后输出结果为：

2

因为输出的是十进制数，它的二进制表示为：

( 0010 ) 2 (0010)_2

(

0

0

1

0

)

2

​

。注意：这里的 前导零 可有可无，作者写上前导零只是为了对齐以及让读者更加清楚位与的运算方式。

2）位或

位或的运算结果如下：

左操作数	右操作数	结果
0	0	0
0	1	1
1	0	1
1	1	1

我们来看以下这段程序：

#include <stdio.h>
int main() {
    int a = 0b1010;
    int b = 0b0110;         
    printf("%d\n", (a | b) );
    return 0;
}

以上程序的输出结果为：

14

即二进制下的

( 1110 ) 2 (1110)_2

(

1

1

1

0

)

2

​

。

3）异或

异或的运算结果如下：

左操作数	右操作数	结果
0	0	0
0	1	1
1	0	1
1	1	0

我们来看以下这段程序：

#include <stdio.h>
int main() {
    int a = 0b1010;       
    int b = 0b0110;          
    printf("%d\n", (a ^ b) ); 
    return 0;
}

以上程序的输出结果为：

12

即二进制下的

( 1100 ) 2 (1100)_2

(

1

1

0

0

)

2

​

。

4）按位取反

按位取反其实就是 0 变 1， 1 变 0。

同样，我们来看一段程序。

#include <stdio.h>
int main() {
    int a = 0b1;
    printf("%d\n", ~a );
    return 0;
}

这里我想卖个关子，同学们可以自己试一下运行结果。

至于为什么会输出这个结果，我会在 光天化日学C语言（17）- 位运算 ~ 的应用 中进行详细讲解。

2、移位位运算

对于移位位运算，总共有两个，如下表所示：

C语言运算符表示	含义	示例
<<	左移	x << y
>>	右移	x >> y

1）左移

其中x << y代表将二进制的

x x

x

的末尾添加

y y

y

个零，就好比向左移动了

y y

y

位。比如

( 1011 ) 2 (1011)_2

(

1

0

1

1

)

2

​

左移三位的结果为：

( 1011000 ) 2 (1011000)_2

(

1

0

1

1

0

0

0

)

2

​

。

2）右移

其中x >> y代表将二进制的

x x

x

从右边开始截掉

y y

y

个数，就好比向右移动了

y y

y

位。比如

( 101111 ) 2 (101111)_2

(

1

0

1

1

1

1

)

2

​

右移三位的结果为：

( 101 ) 2 (101)_2

(

1

0

1

)

2

​

。

原文: https://blog.csdn.net/WhereIsHeroFrom/article/details/122532627