位运算修行手册（一）-阿里云开发者社区

*明明自觉学会了不少知识，可真正开始做题时，却还是出现了“一支笔，一双手，一道力扣（Leetcode）做一宿”的窘境？你是否也有过这样的经历，题型不算很难，看题解也能弄明白，可一到自己做就变成了与题面面相觑无从下手。这就是基础知识掌握不扎实、不牢固导致的，我们以位运算为例，我将把位运算基础给你清楚讲述，再以例题带你实战体验。

一、位与运算符

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

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

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

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

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

所以对于位与来说，只要这一位上有一个 0，这一位的结果就会变成 0。

int main() {
    int a = 0b1010;
    int b = 0b0110;
    printf("%d\n", (a & b) );
    return 0;
}

(1) 在C语言中，以 0b 作为前缀，表示这是一个二进制数。那么 a 的实际值就是 (1010) 。
(2) 同样的， b 的实际值就是 (0110) ；
(3) 那么这里 a & b 就是对 (1010) 和 (0110) 的每一位做表格中的 & 运算。
所以最后输出结果为：
因为输出的是十进制数，它的二进制表示为： (0010)_2。
注意：这里的前导零可有可无，作者写上前导零只是为了对齐以及让读者更加清楚位与的运算方式。

二、位与运算符的应用

1、奇偶性判定

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

int main() {
    if(5 % 2 == 1) {
        printf("5是奇数\n");
    }
    if(6 % 2 == 0) {
        printf("6是偶数\n");
    }
    return 0;
}

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

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

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

所以，我们对任何一个数，通过将它和 0b1 进行位与，结果为零，则必然这个数的二进制末尾位为0，根据以上表就能得出它是偶数了；否则，就是奇数。
注意，由于 if 语句我们还没有实际提到过，所以这里简单提一下，后面会有系统的讲解：
对于以上语句，expr 代表的是一个表达式，表达式的值最后只有零或非零，如果值为非零，才会执行 body中的内容。

2、取末五位

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

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

int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", (x & 0b11111) );
    return 0;
}

那么如果问题变成下面的形式，代码又要怎么写呢？

【例题2】如果是想得到末七位、末九位、末十四位、末 K 位，应该如何实现呢？

3、消除末尾五位

【例题3】给定一个 32 位整数，要求消除它的末五位。

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

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

int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", (x & 0xffffffe0) );
    return 0;
}

提示： f 代表 4 个1； e 代表 3个1,1个0； 0 代表 4 个 0；

4、消除末尾连续1

【例题4】给出一个整数，现在要求将这个整数转换成二进制以后，将末尾连续的1都变成0，输出改变后的数（以十进制输出即可）。

我们知道，这个数的二进制表示形式一定是：

如果，我们把这个二进制数加上1，得到的就是：

我们把这两个数进行位与运算，得到：

所以，你学会了吗？

5、2的幂判定

【例题5】请用一句话，判断一个正数是不是2的幂。

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

这个数的十进制值为 2 的 k 次。
那么我们将它减一，即 2 的 k 次减一的二进制表示如下（参考二进制减法的借位）：

于是这两个数位与的结果为零，于是我们就知道了如果一个数 x 是 2 的幂，那么 x & (x-1) 必然为零。而其他情况则不然。所以本题的答案为：

三、位或运算符

位或运算符是一个二元的位运算符，也就是有两个操作数，表示为 x | y。位或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共 4 种情况。

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

1）无论是 0 或 1，只要位或上 1，就变成1；

2）只有当两个操作数都是0的时候，才变成 0；

int main() {
    int a = 0b1010;
    int b = 0b0110;
    printf("%d\n", (a | b) );
    return 0;
}

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

(2) 同样的，b 的实际值就是 (0110)；

(3) 那么这里 a | b 就是对 (1010) 和 (0110) 的每一位做表格中的 | 运算。

所以最后输出结果为：

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

四、位或运算符的应用

1、设置标记位

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

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

int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x | 0b10000);
    return 0;
}

2、置空标记位

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

当我们学过位与以后，很容易得出这样一种做法：

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) 步可以采用位或运算，而第 (2) 步，我们可以直接用减法即可。代码实现如下：

int main() {
    int x;
    int a = 0b10000;
    scanf("%d", &x);
    printf("%d\n", (x | a) - a );
    return 0;
}

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

3、低位连续零变一

【例题3】给定一个整数 x，将它低位连续的 0 都变成 1。

假设这个整数低位连续有 k 个零，二进制表示如下：

那么，如果我们对它进行减一操作，得到的二进制数就是：

我们发现，只要对这两个数进行位或，就能得到：

也正是题目所求，所以代码实现如下：

int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x | (x-1) );
    return 0;
}

(1) x | (x-1) 就是题目所求的 “低位连续零变一” 。

4、低位首零变一

【例题4】给定一个整数 x，将它低位第一个 0 变成 1。

记得在评论区留下你的答案哦 ~

五、异或运算符

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

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

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

1）两个相同的十进制数异或的结果一定为零。

2）任何一个数和 0 的异或结果一定是它本身。

3）异或运算满足结合律和交换律。

int main() {
    int a = 0b1010;
    int b = 0b0110;
    printf("%d\n", (a ^ b) );
    return 0;
}

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

(2) 同样的， b 的实际值就是 (0110) ；

(3) 那么这里 a ^ b 就是对 (1010) 和 (0110) 的每一位做表格中的 ^ 运算。

所以最后输出结果为：

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

六、异或运算符的应用

1、标记位取反

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

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

int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x ^ 0b1000);
    return 0;
}

2、变量交换

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

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

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        printf("%d %d\n", a, b);
    }
    return 0;
}

我们直接来看 (1) 和 (2) 这两句话，相当于 b 等于 a ^ b ^ b ，根据异或的几个性质，我们知道，这时候的 b 的值已经变成原先 a 的值了。

而再来看第 (3) 句话，相当于 a 等于 a ^ b ^ a，还是根据异或的几个性质，这时候，a 的值已经变成了原先 b 的值。

从而实现了变量 a 和 b 的交换。

3、出现奇数次的数

【例题3】输入 n 个数，其中只有一个数出现了奇数次，其它所有数都出现了偶数次。求这个出现了奇数次的数。

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

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;
}

4、丢失的数

【例题4】给定一个 n-1 个数，分别代表 1 到 n 的其中 n-1 个，求丢失的那个数。

记得在评论区留下你的答案哦 ~

5、简单加密

基于两个数异或为零，任何数和零异或为其本身这两个特点，异或还可以用来做简单的加密。将明文异或上一个固定的数变成密文以后，可以通过继续异或上这个数，再将密文转变成明文。

七、按位取反运算符

取反运算符是一个单目位运算符，也就是只有一个操作数，表示为 ~x。取反运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况。

int main() {
    int a = 0b1;
    printf("%d\n", ~a );
    return 0;
}

这里 ~a 代表的是对二进制数 1 进行取反，直观感受应该是 0。但是实际输出的却是：

-2

这是为什么呢？那是因为，这是一个 32 位整数，实际的取反操作是这样的：00000000 00000000 00000000 00000001

11111111 11111111 11111111 11111110

32位整数的二进制表示，前导零也要参与取反。而对于一个有符号的 32 位整数，我们需要用最高位来代表符号位，即最高位为 0，则代表正数；最高位为 1，则代表负数；

这时候我们就需要引入补码的概念了。

1、补码的概念

在计算机中，二进制编码是采用补码的形式表示的，补码定义如下：

正数的补码是它本身，符号位为 0；负数的补码为正数数值二进制位取反后加一，符号位为一；

2、补码举例

根据补码的定义，-2的补码计算，需要经过两步：

1）对 2 的二进制进行按位取反，如下：00000000 00000000 00000000 00000010

11111111 11111111 11111111 11111101

2）然后加上 1，如下：

11111111 11111111 11111111 11111101

00000000 00000000 00000000 00000001

11111111 11111111 11111111 11111110

结果正好为我们开始提到的 ~1 的结果。

3、补码的真实含义

补码的真实含义，其实体现在 “补” 这个字上，在数学上，两个互为相反数的数字相加等于 0，而在计算机中，两个互为相反数的数字相加等于 2 的 n 次。

换言之，互为相反数的两个数互补，补成 2 的 n 次。

对于 32位整型，n = 32；对于 64 位整型，n = 64。所以补码也可以表示成如下形式：

于是，对于 int 类型，就有：

即：

于是，我们开始数数……

2^32 = 1 00000000 00000000 00000000 00000000

2^32 - 1 = 11111111 11111111 11111111 11111111

2^32 - 2 = 11111111 11111111 11111111 11111110

近一步了解了 -2 的二进制表示。

位运算修行手册（一）+https://developer.aliyun.com/article/1389769

位运算修行手册（一）

一、位与运算符

二、位与运算符的应用

1、奇偶性判定

2、取末五位

3、消除末尾五位

4、消除末尾连续1

5、2的幂判定

三、位或运算符

四、位或运算符的应用

1、设置标记位

2、置空标记位

3、低位连续零变一

4、低位首零变一

五、异或运算符

六、异或运算符的应用

1、标记位取反

2、变量交换

3、出现奇数次的数

4、丢失的数

5、简单加密

七、按位取反运算符

1、补码的概念

2、补码举例

3、补码的真实含义

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

位运算修行手册（一）

一、位与运算符

二、位与运算符的应用

1、奇偶性判定

2、取末五位

3、消除末尾五位

4、消除末尾连续1

5、2的幂判定

三、位或运算符

四、位或运算符的应用

1、设置标记位

2、置空标记位

3、低位连续零变一

4、低位首零变一

五、异或运算符

六、异或运算符的应用

1、标记位取反

2、变量交换

3、出现奇数次的数

4、丢失的数

5、简单加密

七、按位取反运算符

1、补码的概念

2、补码举例

3、补码的真实含义

热门文章

最新文章

相关课程

相关电子书