目錄

一、^ 是什么（^稱為異或）

二、^的規(guī)律(特點)

三、可利用^秒殺的常見例題（重點）

1、消失的數字

?2、不一樣的人生密碼

3、交換兩個數（不能創(chuàng)建中間變量）

4、找出只出現一個的兩個數字

一、^ 是什么（^稱為異或）

是一種操作符，針對二進制異或而言的，兩個數對應的二進制位相同，異或結果為0，不同，異或結果為1。

例如：1^2

1的二進制位：

000000000 00000000 00000000 00000001

2的二進制位：

000000000 00000000 00000000 00000010

?1^2異或后:?

000000000 00000000 00000000 00000011 即為3

異或它在很多題型中都會用的到，我們利用它本身的常見規(guī)律可以秒殺很多題。

二、^的規(guī)律(特點)

特點1、大小相同的數字異或為0，任何數字異或0均為本身(可以自己寫兩個數的二進制位進行驗證)

例如：1^1=0,?2^0=2 ,3^0=3

特點2、A^B^B = A 由1可得2 因為B^B=0 0^A=A

特點3、符合結合律和交換律

三、可利用^秒殺的常見例題（重點）

1、消失的數字

題目描述：數組nums包含從0到n的所有整數(nums是不重復的無序整形數組)，但其中缺失了一個。請找出缺失的那個整數，時間復雜度最大為o(n)。

題目解釋：比如n為3，那么nums數組本應包括0 1 2 3。但你現在可能就包含了0 1 3,假設丟了2(?但其中丟失哪一個你并不知道)，就讓你找丟失的這個2.

思路：0到n每個數^一遍，數組中存在的每一個元素^一遍，兩者再^一下就找到缺失的數字了

比如n=3(假設數組中缺失了2),則0到n每個數^一下即 0^1^2^3

再^數組中存在的每一個元素:0^1^3

兩者再^一下：0^1^2^3 ^ 0^1^3 = 2

這個是根據特點一和特點三推得，因為兩個相同的數^后為0,一個數^0后=本身，所以就找到這個消失的數字了

代碼如下:

#include<stdio.h>
int missingNumber(int* nums, int numsSize)
{
	int i = 0;
	int x = 0;
	for (i = 0; i <= numsSize; i++)
	{
		x ^= i;
	}
	for (i = 0; i < numsSize; i++)
	{
		x ^= nums[i];
	}
	return x;
}
int main()
{	//假設n為3
	int nums[] = { 0,1,3 };
	int n = 0;
	scanf("%d", &n);
	//數組的大小就是n,因為是0~n，本來應該有0 1 2 3的
	// 但現在只有0 1 3所以n就是數組此時的大小
	//如果不缺失一個數字，數組大小是n+1的
	printf("%d",missingNumber(nums, n));
	return 0;
}

?2、不一樣的人生密碼

題目描述：每個人都有一個人生密碼，只有兩個人的人生密碼相同，才能走到一起，給出n個人的人生密碼，n是奇數，其中只有一個人的人生密碼是單獨的，其他都是成對的，請你找出不成對的那一個。(時間限制400ms)

輸入格式：

多組測試，每行第一個數為n(1<=n<=1000000),后面有n個正整數，表示n個人的人生密碼，n值為0時表示輸入結束。

輸出格式：

輸出那個不成對的人生密碼。

輸入樣例：

3 8 9 8

5 120 10 120 10 85

0

輸出樣例:

9

85

思路：這道題跟第一題思路差不多，因為只有一個是單獨的，那么把輸入的所有數^一遍，得到的? 不就是那個單獨的數字，因為兩個相同的數字^后一定為0,那個單獨的數再^0一定得到那個? ? 單獨的數了 ,但是要考慮只有一個數字的話，就不用^了，直接找到了

代碼如下：

#include<stdio.h>

int main()
{
	int ret = 0, n = 0,i = 0,x = 0;
	while (~scanf("%d", &n) && n != 0)
	{//判斷這么寫是因為&&具有左結合性
		ret = 0;//每組測試前一定要先初始化為0
		if (n == 1)
		{//只有一個數就不需要^去掉成對的了
			scanf("%d", &x);
			printf("%d\n", x);
			continue;
		}
		for (i = 0; i < n; i++)
		{
			scanf("%d", &x);
			ret ^= x;
		}
		printf("%d\n", ret);
	}
	return 0;
}

3、交換兩個數（不能創(chuàng)建中間變量）

?題目要求：不能創(chuàng)建中間變量交換兩個數

思路：運用特點二A^B^B=A和特點三的交換律即可求解

#include<stdio.h>
int main()
{
	int a = 0, b = 0;
	a = a ^ b;
	b = b ^ a;//b=b^ a^b=a
	a = a ^ b;//a=a^ a^b=b
	return 0;
}

4、找出只出現一個的兩個數字

題目描述：一個整形數組arr里除了兩個數字只出現一次外，其他數字都出現了兩次。請你找出這兩個只出現一次的數字。要求時間復雜度：o(n),空間復雜度:o(1)。

如 int arr[] = {1,1,2,2,3,3,4,5,5,6,7,7,8,8,9,9}

則這兩個你要找的數字為4,6

思路：要返回兩個值，可以返回一個儲存這兩個值的數組，即指針。那么這道題其實就是在第二題不一樣的人生密碼上加了一點難度，第二題是找一個（找一個就很好處理了），而這道題是找兩個。難就難在兩個怎么處理，我們可以試試把這兩個數字分離，轉換成兩組，每一組都是一道"不一樣的人生數字"的題，即這兩組，第一組包含了第一個只出現1次的數字，第二組包含了第二個只出現1次的數字。（因為只出現一次，說明這兩個數肯定不相同，所以可以分離)。重點是如何分離

————? 分離這兩個數的過程? ————

我們只需找到這兩個數不同的一個二進制位就可以，怎么找？兩個數^后的結果中二進制位為1的，就說明兩個數原來的這個位置的二進制位不同（肯定一個是0，一個是1） ，我們只需找到一個兩者^后為1的二進制位即可。只要數組中元素對應的這個二進制位為1的數值分到一組，為0的分到另一組。我們就可以把這兩個只出現一次的數區(qū)分為兩組。那么這兩組就變成：第一組有第一個數和其他n組成對的數，第二組有第二個數和其他m組成對的數。這下是不是就變成兩個“不一樣的人生密碼”的例題2了吧？求兩次是不是就可以了！

代碼如下：

注：詳細的代碼理解全在代碼中！文章來源地址http://www.zghlxwxcb.cn/news/detail-605264.html

#include<stdio.h>
#include<stdlib.h>

int* Find(int* arr, int numSize)
{
//1、得到兩個只出現一次的數^后的結果
	int x = 0, i = 0;
	for (i = 0; i < numSize; i++)
	{
		x ^= arr[i];//得到兩個只出現一次的數的^后的結果
	}
//2、定位這個結果中一個二進制位為1時,需要x向右移多少位的m
	int m = 0;
	for (i = 0; i < 32; i++)
	{//x是兩個只出現一次的數^后的結果
	 //x >> i & 1即這兩個數不同的對應的一個二進制位數
	 //而我們現在要找這個二進制位數是幾，賦給m
		if ((x >> i & 1) == 1)//別忘了要加(),因為&優(yōu)先級比==優(yōu)先級低
		{//x>>i是遍歷x的32位二進制位的意思，而我們要的是
         //x向右多少位的二進制才為1，我們找到一個二進制為1的即可
			m = i;
			break;
		}
	}
//3、將這兩個只出現一次的數分為兩組
	int x1 = 0, x2 = 0;
	for (i = 0; i < numSize; i++)
	{
		if ((arr[i] >> m & 1) == 1)
		{
			x1 ^= arr[i];
			//這一組中成對的數^后會變?yōu)?
			//所以x1最后的結果為兩個出現一次的數的其中一個
		}
		if ((arr[i] >> m & 1) == 0)
		{
			x2 ^= arr[i];
			//這一組中成對的數^后會變?yōu)?
			//所以x2最后的結果為兩個出現一次的數的另一個
		}
	}
//4、創(chuàng)建數組返回這兩個值
	int* a = (int*)malloc(sizeof(int)*2);
	//動態(tài)開辟，出了函數不會銷毀
	//如果是靜態(tài)開辟，出了函數，雖然原來a的地址還在，但是他的內容已經不屬于a了
	//典型的返回棧空間地址帶來的危害
	if (a != NULL)
	{
		a[0] = x1;
		a[1] = x2;
	}
	else
		exit(-1);
	return a;
}
int main()
{
	int arr[] = { 1,1,2,2,3,3,4,5,5,6,7,7,8,8,9,9 };
	int size = sizeof(arr) / sizeof(arr[0]);
	int* ptr = Find(arr, size);
	printf("%d %d", ptr[0], ptr[1]);
	free(ptr);
	ptr = NULL;
	return 0;
}

到了這里，關于【c語言操作符系列1】^(異或操作符)講解和多種例題詳解的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！