C中的XOR运算符



在进行逐位操作时,我很难确定何时使用XOR运算符。Bitwise And和Or非常直接。如果要屏蔽位,请使用按位AND(常见的使用情况是IP寻址和子网掩码)。如果要打开位,请使用inclusive或。然而,XOR总是让我着迷,我觉得如果在面试中被问到一个需要使用XOR的问题,我永远不会得到它。有人能告诉我什么时候使用它以及一些常见的用例吗。

您使用exclusive或来翻转位-打开的位被关闭,反之亦然。例如,这可以方便地交换两个数字,而不需要为第三个数字留出空间。

0x0A ^ 0xFF = 0x03 ( 00001010 ^ 11111111 = 11110101 )

交换号码:

operation   example 
A      B
initial:   0011    1010
a = a^b;   1001    1010
b = a^b;   1001    0011
a = a^b;   1010    0011

正如你所看到的,数字(在这种情况下是半字节)A和B是在不使用额外空间的情况下交换的。这适用于任何两个相同类型的数字(尽管在C中,逐位运算符需要无符号整数)

XOR运算也用于"弱加密"。您可以对一个字符串与一个(重复的)"码字"进行XOR,结果将是一个毫无意义的字节字符串。再次应用相同的操作,将显示原始操作。这是一个相当弱的算法,不应该在现实生活中使用。

关于切换位——在"旧时代",如果你想反转图像,你可以对每个像素执行pix = pix & 1,或者如果你可以一次执行一个字节,则为byte = byte & 0xFF。这将把白色背景上的黑色文本变成黑色背景上的白色文本。我认为ATARI有一项专利,通过对位图进行异或运算,可以在"屏幕上的任何地方"创建闪烁的光标。

类似地,如果你有一个微控制器想要创建一个闪烁的灯,重复执行state = state XOR 1将导致状态切换。

最后,有许多依赖XOR运算的"bit twidddling hack"。例如,计算一个字的奇偶性(即,设置比特的数量是奇数还是偶数)可以用以下方法完成(来源:http://graphics.stanford.edu/~seander/bithacks.html)

unsigned int v;  // word value to compute the parity of
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;

还有许多其他"聪明的把戏"——当你试图找到最快的方法来做一些涉及比特操作的事情时,它们通常会出现。大多数人都可以在没有真正"得到"的情况下过得很好,这没关系。我,我喜欢摆弄。

除了交换两个数字和其他答案解释的位切换之外,XOR还用于在不使用if语句的情况下查找两个数字的最大值

int max(int x, int y)
{
return x ^ ((x ^ y) & -(x < y)); 
}

在创意方面,XOR运算通常用于基于给定点的当前X和Y坐标绘制简单的正方形图形。例如,一个单元格大小可变的棋盘图案:

#include <stdio.h>
#define CELLSIZE 2   /* cell size is actually 2 power CELLSIZE */
#define MASK (1<<CELLSIZE)
int main()
{
int i,j;
for (i=0;i<32;i++)
{
for (j=0;j<32;j++)
putchar (' '+('*'-' ')*( ((i&MASK)^(j&MASK))!=0 ) );
putchar ('n');
}
return 0;
}
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****

在视频游戏编码中,当你没有硬件精灵和/或多个游戏场时,在位图背景顶部绘制精灵的最简单方法是将精灵像素与背景像素异或(一个像素由一位编码),这样你就可以在方便的时候擦除它,而不必存储精灵修改的屏幕部分。要擦除精灵,只需在相同的坐标处再次绘制即可。这种方法也可以用于在一些非加速显示硬件上渲染鼠标指针。

我最喜欢的例子之一是就地交换。(注意:这是C++代码,不是C代码,但你明白了。)

void swap(int &x, int &y)
{
x ^= y;
y ^= x;
x ^= y;
}

您也可以切换单个位:(n是第n位,在b中切换)

a = b ^ (1 << n)

另一个不太常见的用途:XOR链表:

  • 您可以保留下一个和上一个项目的XOR,而不是保留每个项目的指针。这些天,我们有太多的记忆,这可能无关紧要,但嘿,它仍然有点酷。(除非你在嵌入式系统上,并且由于某种原因需要一个双链接列表。然后你会很高兴读到这篇文章。)

XOR的应用尤其可以看到,当一个数组中除了一个之外的每个数字都重复,并且要找到未重复的单个数字时。对所有的数字进行异或运算会得到只出现一次的数字。

int arr[]={1, 1, 2, 2, 3, 3, 4};
// frequency of every number in the array is 2 except one number.
int sz=7; //size of array
int x=0; 
for(int i=0;i<sz;i++)
x^=arr[i];
// x would give the number 4 here 

最新更新