位运算
#C 2024-09-01

位运算符

位运算.png

a >> 1 如果没有超出类型范围，代表 a = a / 2

a << 1 如果没有超出类型范围，代表 a = a * 2

异或运算常用特性

异或运算的性质.png

常见面试算法题

（一）如何获取一个数字最右侧的 1 ？

1
int xor = a & (-a)

xor 就代表了整数 a 的二进制表示中最右边的 1 所在的位置（以二进制形式表示），其中对应的二进制中 1 所处的位置表示整数 a 最右侧的 1 的 位置，剩下的全部为 0。

最右侧的1.png

注：补码即原码取反再加1，C语言中的负数就是用补码表示

（二）分离奇偶数

奇数和偶数的二进制特点就是，奇数必然在第一位为 1，而偶数必然在第一位为 0。

1
2
3
bool is_odd(int num) {
	return (num & (-num)) == 1;
}

上述函数就可以判断是否为奇数。取最右侧的数字 1 的位置，如果结果等于 1，代表这个数的二进制第一位就是标记为 1，代表必然为奇数。

（三）如何将数组中不同的两个数找到（其余元素两两出现）？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void get_diff_nums(int *data,int length) {
	int result = 0;
	// 得到两个数
	for (int i = 0; i < length; i++) {
		result ^= data[i];
	}
	// 将两个数分离出来
	int num1 = 0;
	int num2 = 0;
	int xor = result & (-result);
	for (int i = 0; i < length; i++) {
		if (data[i] & xor) {
			num1 ^= data[i];
		}
		else {
			num2 ^= data[i];
		}
	}

	printf("num1 = %d , num2 = %d\n", num1, num2);
}
  1. 异或会把相同的两个数抵消，所以全部元素异或之后，result = 3 ^ 5
  2. 那我们需要想办法把两个数分离出来，两个不同的数，必然至少会有一位不同。即在这一位上，如果你是 0，那么我就是 1（不是南通，别误会）。这样的两个数异或，这个位置会被 1 标识（0 和 1 异或为 1），那就利用 result & (-result) 找到这个位置，这是区分两个数的关键所在。
  3. xor 的二进制中，除了用以区分两个数的位置被标记为 1 ，其余全部为 0。所以我们遍历数组，和 xor 进行 & 操作。相同的两个数必然会被分到一组，且会因为异或而抵消。不同的两个数，会因为 & 计算分离出来。

也许“不同的两个数，会因为 & 计算分离出来”会让人不解。我们知道现在的 xor = 0010，而 3 = 0011，5 = 0101。xor 与之 & 得到的结果为某个数为大于 0，某个数等于0，这就将两个数分离出来了。