在什么情况下可能需要使用按位异或运算符？

Question

在进行按位操作时，我在确定何时使用 XOR 运算符时遇到一些困难。按位与和或非常简单。当您想要屏蔽位时，请使用按位 AND（常见用例是 IP 寻址和子网掩码）。当您想要打开位时，请使用包含或。然而，XOR 总是让我明白，我觉得如果在面试中被问到一个需要使用 XOR 的问题，我永远不会明白。有人可以阐明何时使用它以及一些常见的用例吗？

Answer 1

您可以使用异或来翻转位 - 打开的位将被关闭，反之亦然。例如，这可以方便地交换两个数字而没有空间容纳第三个数字。

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 中，按位运算符期望无符号整数）

异或运算也用于“弱加密”。您可以将字符串与（重复的）“代码字”进行异或，结果将是一串毫无意义的字节。再次应用相同的操作，就会出现原来的情况。这是一个相当弱的算法，永远不应该在现实生活中使用。

关于切换位 - 在“过去”，如果你想反转图像，你可以为每个像素执行

pix = pix & 1

- 或者如果你可以一次执行一个字节，

byte = byte & 0xFF

。这会将白色背景上的黑色文本变成黑色背景上的白色文本。我认为 ATARI 拥有一项专利，可以通过与位图进行异或来在“屏幕上的任何位置”创建闪烁的光标。

同样，如果您有一个微控制器想要创建闪烁的灯光，重复执行

state = state XOR 1

将导致状态切换。

最后，有许多依赖于异或运算的“位旋转黑客”。例如，计算一个字的奇偶校验（即设置的位数是奇数还是偶数）可以通过以下方式完成（来源：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;

还有许多其他“聪明的技巧”——当您试图找到最快的方法来完成涉及位操作的事情时，它们通常会出现。大多数人都可以完美地度过一生，但没有真正“得到”它，这没关系。我，我喜欢摆弄。

Answer 2

在创意方面，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;
}

    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
    ****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****
****    ****    ****    ****

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

Answer 3

除了交换两个数字和位切换之外，如其他答案按位解释的那样

XOR

还用于在不使用

if

语句的情况下查找两个数字的最大值

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

Answer 4

我最喜欢的例子之一是就地交换。 （注意：这是 C++ 代码，不是 C 代码，但你明白了。）

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

您还可以切换单个位：（

n

是第n位，在

b

中切换）

a = b ^ (1 << n)

另一个不太常见的用途：异或链接列表：

• 您可以按住下一个和上一个项目的异或，而不是按住每个项目的指针。如今，我们拥有如此多的内存，这可能并不重要，但是嘿，它仍然很酷。 （除非您使用的是嵌入式系统并且出于某种原因需要一个双向链表。那么您会很高兴读到这篇文章。）

Answer 5

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