c++中的抑或运算

一、简介

• 符号：^
• 逻辑关系：1^1=0  1^0=1  0^1=1  0^0=0     （即：当A、B不同时为1，相同时为0）
• 运算法则：

1. 交换律：a^b=b^a
2. 结合律：a^b^c=a^(b^c)=(a^b)^c
3. d=a^b^c  =>  a=d^b^c
4. 自反性：a^b^a=b

• 作用：

1. 在交换两个变量的值时，无需引入中间变量。可以利用抑或运算的自反性解决问题。
2. 可以判断一个二进制数a中为1的位数是奇还是偶：a=1010 => b=1^0^1^0=0 => 偶数个1

• 特别注意：抑或运算是在二进制的环境下进行的。如果输入两个十进制数，抑或运算会先转换成二进制，再按位抑或。所以如果只看十进制的话，可能找不到什么规律。

二、例题

落单的数

题目描述 Description

有n个数(n是奇数)，其中n-1个数两两成对，有1个数落单，找出这个数。要求O(n)的时间复杂度，O(1)的空间复杂度

 

输入描述 Input Description

第一行输入一个n， n是大于等于1的奇数

第二行包含n个整数

 

输出描述 Output Description

输出那个落单的数

 

样例输入 Sample Input

3

1 7 1

 

样例输出 Sample Output

7

 

数据范围及提示 Data Size & Hint

1<=n<=4000001  n是一个奇数

 

单是这一道题的意义并不大，但是解题方法可以当做模板，以后有需要的直接用。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 using namespace std;
 8 
 9 int main()
10 {
11     int n,ans=0;
12     scanf("%d",&n);
13     for(int i=1;i<=n;i++)
14     {
15         int x;
16         scanf("%d",&x);
17         ans=ans^x;
18     }
19     printf("%d",ans);
20     //system("pause");
21     return 0;
22 }

codevs 3295