【C语言】【算法】利用异或找不同单一数据

异或的性质

  1. a^a=0;
  2. a^0=a;
  3. a^b=b^a,即交换律;

入门问题

问题描述

有一组数据,其中某些数据出现两次,只有一个数据出现过一次,请找出它。如:

arr[] = {1, 4, 2, 2, 4};
// 结果应为1

解决方法

由上面异或的性质,可以这样做:将所有元素进行异或,其结果就是出现一次的那个数。

void find_number_v1()
{
	int arr[] = {3, 4, 5, 9, 3, 5, 4};
	int i, target = 0;
	for (i = 0; i < sizeof(arr)/sizeof(int); ++i) {
		target = target ^ arr[i];
	}
	printf("target = %d\n", target);
	// 3出现4次,异或为0;4出现2次,异或为0;1出现3次,异或为1;
	int arr2[] = {3, 3, 1, 4, 3, 4, 3, 1, 1};
	target = 0;
	for (i = 0; i < sizeof(arr2)/sizeof(int); ++i) {
		target = target ^ arr2[i];
	}
	printf("target = %d\n", target);
}

问题延伸

只要保证目标数据出现的次数是奇数次,其它数据出现的次数是偶数次都可以根据这种方法找出目标数据;

进阶问题

问题描述

还是一组数据,有些数据出现两次,有两个不同的数据只出现一次,请找出这两个数据(A和B)。

解决方法

可以把数据分为两组,将A和B分到不同的组,然后再按第一种方法找出来给你个数据。可是如何将A,B分到不同的组中去呢?

一般想法都是这样的:找到A和B之间的一个数C,然后大于C为一组,小于C为另一组,这样A和B就被分开。但是现在A和B都不知道啊?怎么办呢?只要找到一个A,B的不同点即可,这样就可以区分A和B。是否可以从两个数异或的结果C中找到标识这两个数不同的特点呢?答案是可以的。

  1. C是A和B异或的结果,为11的地方说明两者的不同之处,我们只需要找到一个不同点即可;
  2. 从右至左,找到C中第一位不为0的位置,记为kk,说明A和B在第kk位不相同;
  3. 截取从第0位到第kk位,组成一个数D;
  4. 用数D通过相与的方法就可以区分A和B了,一个结果比为0,一个结果为1。

如:

 // A = 5 =      1001
 // B = 2 =       0010
 // D = A^B = 1011
 // E = 1
 // A&E = 1
 // B&E = 0
// 这样就把A和B分开了,其它数据被分到那一组不重要,因为是成对的,最终可以被异或为0。

代码实现:

void find_number_v2()
{
	// 目标数是8和2
        int arr[] = {12, 3, 8, 3, 4, 9, 10, 9, 4, 10, 12, 2};
	int pivot = 0;
	unsigned int i = 0;
	// 1. 得到整组数据的异或值
	for (i = 0; i < sizeof(arr)/sizeof(int); ++i) {
		pivot = pivot ^ arr[i];
	}
	i = 0;
	// 2. 找到pivot第一位不为0的位置
	while(!(pivot & (1 << i))) {
		i++;
	}
	// 3. 将第一位不为0的右边取出,作为pivot(此pivot可以区分A和B)
	pivot = (1 << i);
	// 4. 将A和B分到两个不同的组,其它的数据都是成对的,无所谓
	for (i = 0; i < sizeof(arr)/sizeof(int); ++i) {
		// pivot&arr[i] >= 1
		if (pivot&arr[i]) {
			//left[] = arr[i];
			printf("L:>>arr[%d]=%d\n", i, arr[i]);
		} else {
			//right[] = arr[i];
			printf("\t\t\tR:>>arr[%d]=%d\n", i, arr[i]);
		}
	}

	// 5. 然后再对left和right分别用异或即可得出两个不同的数字。
}

再对两组数据的所有元素进行异或即可。

问题延伸

只要保证其它数据出现偶数次即可,那两个数出现奇数次即可。

如果要有3个不同的数呢?

交换两数

/**
 *	 主要原理:
 *	 	a = a ^ b;		//找到a和b不相同的bit,并且这些bit都是1
 *	 	b = a ^ b;		//那么b就等于把a与b不同的位置取反
 *	 	a = a ^ b;		//现在b等于a了,那么a就等于把b与a不同的位置取反
 *	 	1. 把a和b都展开成bit的形式
 *	 	2. 找到a和b的bit不同的位置,这些位置都被置为1
 *	 	3. 把a与b不同的位置取反就是b,同理也是一样的
 *	 	a = 4 = 0100;
 *	 	b = 8 = 1000;
 *
 * 		a = a^b = 1100;		//a和b不同的就是bit2和bit3
 * 		b = a^b = 0100;		//b就等于把a的bit2和bit3取反,由于bit2和bit3都为1,所以异或=取反
 * 		a = a^b = 1000;		//同理
 *
 * 优点:速率快,不需要其它作为temp
 * 缺点:只能用于整形,浮点型进行转换的话会有误差。
 * @Author   CofCai
 * @DateTime 2021-01-04T20:21:27+0800
 */
void swap_two_num()
{
	int a = 10, b = -151;
	a = a^b;
	b = a^b;
	a = a^b;
	printf("a = %d\tb = %d\n", a, b);

	float x = 10.2, y = 203.23;
	x = x*100;
	y = y*100;
	x = (int)(x)^(int)(y);
	y = (int)(x)^(int)(y);
	x = (int)(x)^(int)(y);
	printf("x = %f\ty = %f\n", x/100, y/100);
}

对于上面的缺点(只能转换整形数),其实是可以解决的。因为浮点数在计算机存储的还是二进制形式,而异或的对象就是二进制形式,所以原理上还是可以通过异或交换两个数。

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

// 如果传入的x、y是char类型,那么结果会有问题,因为char类型
// 转为int类型,字节数增加,增加的字节的内容是未知的。
// 所以,要保证x、y的字节数和int类型所占的字节数相等。
// char类型的可以直接异或,即c = c1^c2是不会报错的。
#define SWAP_NUM(x, y)	({				\
	*(int*)(&x) = *(int*)(&x) ^ *(int*)(&y);	\
	*(int*)(&y) = *(int*)(&x) ^ *(int*)(&y);	\
	*(int*)(&x) = *(int*)(&x) ^ *(int*)(&y);	\
})

int main(int argc, char const *argv[])
{
	char c1 = '2', c2 = 'a';
	int a = 7455, b = 23;
	float m = 2.32, n = -77.23;
	c1 = c1^c2;
	c2 = c1^c2;
	c1 = c1^c2;
	printf("c1 = %c, c2 = %c\n", c1, c2);

	SWAP_NUM(a, b);
	printf("a = %d, b = %d\n", a, b);

	SWAP_NUM(m, n);
	printf("m = %f, n = %f\n", m, n);

	return 0;
}

赞赏