☀️光天化日学C语言☀️(16)- 位运算 ^ 的应用 | 最神奇的异或运算

英雄哪里出来 发表于 2021/07/16 07:35:34 2021/07/16
【摘要】 最神奇的异或运算

一、前言

  本文作者是从 2007 年开始学 C语言 的,不久又接触了C++,基本就是 C/C++ 技术栈写了 14 年的样子,不算精通,但也算差强人意。著有《夜深人静写算法》系列,且承诺会持续更新,直到所有算法都学完。主要专攻 高中 OI 、大学 ACM、 职场 LeetCode 的全领域算法。由于文章中采用 C/C++ 的语法,于是就有不少读者朋友反馈语言层面就被劝退了,更何况是算法。
  于是,2021 年 06 月 12 日,《光天化日学C语言》 应运而生。这个系列文章主要服务于高中生、大学生以及职场上想入坑C语言的志同道合之人,希望能给祖国引入更多编程方面的人才,并且让自己的青春不留遗憾!
  这一章的主要内容是异或运算符的应用。

二、人物简介

  • 第一位登场的就是今后会一直教我们C语言的老师 —— 光天。
  • 第二位登场的则是今后会和大家一起学习C语言的没什么资质的小白程序猿 —— 化日。

三、异或运算符

  • 异或运算符是一个二元的位运算符,也就是有两个操作数,表示为x ^ y
  • 异或运算会对操作数的每一位按照如下表格进行运算,对于每一位只有 0 或 1 两种情况,所以组合出来总共 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) 在C语言中,以0b作为前缀,表示这是一个二进制数。那么a的实际值就是 ( 1010 ) 2 (1010)_2
  • ( 2 ) (2) 同样的,b的实际值就是 ( 0110 ) 2 (0110)_2
  • ( 3 ) (3) 那么这里a ^ b就是对 ( 1010 ) 2 (1010)_2 ( 0110 ) 2 (0110)_2 的每一位做表格中的^运算。
  • 所以最后输出结果为:
12
  • 因为输出的是十进制数,它的二进制表示为: ( 1100 ) 2 (1100)_2

四、异或运算符的应用

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 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) ( 2 ) (2) 这两句话,相当于b等于a ^ b ^ b,根据异或的几个性质,我们知道,这时候的b的值已经变成原先a的值了。
  • 而再来看第 ( 3 ) (3) 句话,相当于a等于a ^ b ^ a,还是根据异或的几个性质,这时候,a的值已经变成了原先b的值。
  • 从而实现了变量ab的交换。

3、出现奇数次的数

【例题3】输入 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;
}

4、丢失的数

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

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

5、简单加密

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

通过这一章,我们学会了:
  1)用位运算 ^ 来做标记位的取反;
  2)用位运算 ^ 来做变量交换;
  3)用位运算 ^ 找出出现奇数次的数;
  4)用位运算 ^ 的加密解密;

  • 希望对你有帮助哦 ~ 祝大家早日成为 C 语言大神!

课后习题


📢博客主页:https://blog.csdn.net/WhereIsHeroFrom
📢欢迎各位 👍点赞 ⭐收藏 📝评论,如有错误请留言指正,非常感谢!
📢本文由 英雄哪里出来 原创,转载请注明出处,首发于 🙉 CSDN 🙉
作者的专栏:
  👉C语言基础专栏《光天化日学C语言》
  👉C语言基础配套试题详解《C语言入门100例》
  👉算法进阶专栏《夜深人静写算法》

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。