按位 XOR（异或）是什么意思？
我试图理解 C# 或一般情况下的二元运算符，特别是 ^ -独占或。
例如：
给定一个正整数数组。除了一个出现奇数次的数字外，所有数字都出现偶数次。在 O(n) 时间和常数空间中求出该数。
这可以通过 ^ 来完成，如下所示：对所有元素进行按位异或。最后我们得到出现奇数的数字。
它是如何运作的？
当我这样做时：
int res = 2 ^ 3;
res = 1;
int res = 2 ^ 5;
res = 7;
int res = 2 ^ 10;
res = 8;
到底发生了什么？还有哪些其他位魔法？我可以查找并了解更多有关它们的参考资料吗？
I'm trying to understand the binary operators in C# or in general, in particular ^ - exclusive or.
For example:
Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time and constant space.
This can be done with ^ as follows: Do bitwise XOR of all the elements. Finally we get the number which has odd occurrences.
How does it work?
When I do:
int res = 2 ^ 3;
res = 1;
int res = 2 ^ 5;
res = 7;
int res = 2 ^ 10;
res = 8;
What's actually happening? What are the other bit magics? Any reference I can look up and learn more about them?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
我知道这是一篇相当旧的帖子，但我想简化答案，因为我在寻找其他东西时偶然发现了它。
XOR（异或/非或），可以简单地翻译为切换开/关。
这将排除（如果存在）或包含（如果不存在）指定的位。
使用 4 位 (1111)，我们得到从 0-15 的 16 种可能结果：
十进制值二进制值的左边是 XOR 和其他按位运算中使用的数值，表示相关位的总值。请参阅计算机编号格式和二进制数 - 十进制 了解更多详细信息。
例如：
0011表示位 1 和 2 为开，位 4 和 8 为关。它表示为3的十进制值来表示打开的位，并以扩展形式显示为1+2。至于 XOR 背后的逻辑是怎么回事，这里有一些例子
来自原始帖子
更多示例
I know this is a rather old post but I wanted simplify the answer since I stumbled upon it while looking for something else.
XOR (eXclusive OR/either or), can be translated simply as toggle on/off.
Which will either exclude (if exists) or include (if nonexistent) the specified bits.
Using 4 bits (1111) we get 16 possible results from 0-15:
The decimal value to the left of the binary value, is the numeric value used in XOR and other bitwise operations, that represents the total value of associated bits. See Computer Number Format and Binary Number - Decimal for more details.
For example:
0011are bits 1 and 2 as on, leaving bits 4 and 8 as off. Which is represented as the decimal value of3to signify the bits that are on, and displayed in an expanded form as1+2.As for what's going on with the logic behind XOR here are some examples
From the original post
Further examples
要了解其工作原理，首先需要以二进制形式编写两个操作数，因为按位运算适用于各个位。
然后，您可以为您的特定运算符应用真值表。它作用于两个操作数中具有相同位置（相同位置值）的每对位。因此，
A的最左边位 (MSB) 与B的 MSB 相结合，产生结果的 MSB。示例：
2^10：结果为 8。
To see how it works, first you need to write both operands in binary, because bitwise operations work on individual bits.
Then you can apply the truth table for your particular operator. It acts on each pair of bits having the same position in the two operands (the same place value). So the leftmost bit (MSB) of
Ais combined with the MSB ofBto produce the MSB of the result.Example:
2^10:And the result is 8.
证明这一点的另一种方法是使用 XOR 代数；您不需要了解有关各个位的任何信息。
对于任何数字 x、y、z：
XOR 是可交换的：
x ^ y == y ^ xXOR 是结合律：
x ^ (y ^ z) == (x ^ y) ^ z恒等式为 0：
x ^ 0 == x每个元素都是其自身的逆元素：
x ^ x == 0鉴于此，它是很容易证明所陈述的结果。考虑一个序列：
a ^ b ^ c ^ d ...由于 XOR 是可交换和结合的，因此顺序并不重要。所以对元素进行排序。
现在，任何相邻的相同元素
x ^ x都可以替换为0（自逆属性）。并且任何0都可以被删除（因为它是身份）。尽可能长时间地重复。任何出现偶数次的数字都有整数个对，因此它们都变成0并消失。
最终只剩下一个元素，即出现奇数次的元素。每次它出现两次，那两次就会消失。最终你只剩下一个事件。
[更新]
请注意，这个证明只需要对操作进行某些假设。具体来说，假设带有运算符
.的集合 S 具有以下属性：结合性：
x 。 (y . z) = (x . y) 。 z对于 S 中的任何x、y和z。身份：存在单个元素
e 使得 <代码>e 。 x = x 。 e = x对于 S 中的所有x。闭包：对于 S 中的任何
x和y，x 。 y也在 S 中。自逆：对于 S 中的任何
x，x 。 x = e事实证明，我们不需要假设交换律；我们可以证明这一点：
现在，我说“你不需要了解各个位的任何信息”。我认为任何满足这些属性的群就足够了，并且这样的群不一定与 XOR 下的整数同构。
但@Steve Jessup 在评论中证明我错了。如果您将标量乘以 {0,1} 定义为：
...则此结构满足所有 整数 mod 2 上的向量空间公理。
因此，任何此类结构都同构于按分量异或的一组位向量。
The other way to show this is to use the algebra of XOR; you do not need to know anything about individual bits.
For any numbers x, y, z:
XOR is commutative:
x ^ y == y ^ xXOR is associative:
x ^ (y ^ z) == (x ^ y) ^ zThe identity is 0:
x ^ 0 == xEvery element is its own inverse:
x ^ x == 0Given this, it is easy to prove the result stated. Consider a sequence:
a ^ b ^ c ^ d ...Since XOR is commutative and associative, the order does not matter. So sort the elements.
Now any adjacent identical elements
x ^ xcan be replaced with0(self-inverse property). And any0can be removed (because it is the identity).Repeat as long as possible. Any number that appears an even number of times has an integral number of pairs, so they all become 0 and disappear.
Eventually you are left with just one element, which is the one appearing an odd number of times. Every time it appears twice, those two disappear. Eventually you are left with one occurrence.
[update]
Note that this proof only requires certain assumptions about the operation. Specifically, suppose a set S with an operator
.has the following properties:Assocativity:
x . (y . z) = (x . y) . zfor anyx,y, andzin S.Identity: There exists a single element
esuch thate . x = x . e = xfor allxin S.Closure: For any
xandyin S,x . yis also in S.Self-inverse: For any
xin S,x . x = eAs it turns out, we need not assume commutativity; we can prove it:
Now, I said that "you do not need to know anything about individual bits". I was thinking that any group satisfying these properties would be enough, and that such a group need not necessarily be isomorphic to the integers under XOR.
But @Steve Jessup proved me wrong in the comments. If you define scalar multiplication by {0,1} as:
...then this structure satisfies all of the axioms of a vector space over the integers mod 2.
Thus any such structure is isomorphic to a set of vectors of bits under component-wise XOR.
这是基于一个简单的事实：数字与其自身的异或结果为零。
数字与 0 的异或结果是数字本身。
所以，如果我们有一个数组 = {5,8,12,5,12}。
5 出现了 2 次。
8 出现 1 次。
12 出现了 2 次。
我们必须找到出现奇数次的数字。显然，8就是这个数字。
我们从 res=0 开始，并对数组的所有元素进行异或。
int res=0；for(int i:数组)
res = res ^ i;
This is based on the simple fact that XOR of a number with itself results Zero.
and XOR of a number with 0 results the number itself.
So, if we have an array = {5,8,12,5,12}.
5 is occurring 2 times.
8 is occurring 1 times.
12 is occurring 2 times.
We have to find the number occurring odd number of times. Clearly, 8 is the number.
We start with res=0 and XOR with all the elements of the array.
int res=0;for(int i:array)
res = res ^ i;
按位运算符将整数值内的位视为微小的位数组。这些位中的每一个都像一个微小的
bool值。当您使用按位异或运算符时，该运算符的作用的一种解释是：该位最终效果是单个位开始 < code>false 如果“切换”的总数是偶数，那么最后仍然是
false。如果“切换”总数为奇数，则最后将为true。只要想想“布尔值的微小数组”，它就会开始有意义。
The bitwise operators treat the bits inside an integer value as a tiny array of bits. Each of those bits is like a tiny
boolvalue. When you use the bitwise exclusive or operator, one interpretation of what the operator does is:The net effect is that a single bit starts out
falseand if the total number of "toggles" is even, it will still befalseat the end. If the total number of "toggles" is odd, it will betrueat the end.Just think "tiny array of boolean values" and it will start to make sense.
XOR（异或）运算符在位上的定义是：
一种想象的方式是，右侧的“1”改变左侧的位，右侧的“0”改变side 不会改变左侧的位。然而，XOR 是可交换的，所以如果两边颠倒也是如此。
由于任何数字都可以用二进制形式表示，因此任何两个数字都可以进行异或运算。
为了证明它是可交换的，您可以简单地查看它的定义，并看到对于任一侧的每个位组合，如果两侧改变，结果是相同的。为了证明它是关联的，您可以简单地运行所有可能的组合，将 3 位进行异或运算，无论顺序如何，结果都将保持不变。
现在，正如我们证明了上面的那样，让我们看看如果我们对相同的数字本身进行异或会发生什么。由于该操作适用于各个位，因此我们可以仅对两个数字进行测试：0 和 1。
因此，如果将一个数字与其自身进行异或，则总是得到 0（无论您相信与否，但 XOR 的属性已被编译器，当需要将 0 加载到 CPU 寄存器时，执行位操作比显式将 0 推入寄存器要快，编译器只会生成将寄存器异或到其自身的汇编代码。
现在，如果 X XOR X 为 0，并且 XOR 是关联的，那么您需要找出所有其他数字都已重复两次（或任何其他奇数次）的数字序列中哪个数字没有重复。如果我们将重复的数字放在一起，它们将异或为 0。与 0 进行异或的任何内容都将保留其本身。因此，在对这样的序列进行异或运算后，您最终将得到一个不重复（或重复偶数次）的数字。
The definition of the XOR (exclusive OR) operator, over bits, is that:
One of the ways to imagine it, is to say that the "1" on the right side changes the bit from the left side, and 0 on the right side doesn't change the bit on the left side. However, XOR is commutative, so the same is true if the sides are reversed.
As any number can be represented in binary form, any two numbers can be XOR-ed together.
To prove it being commutative, you can simply look at its definition, and see that for every combination of bits on either side, the result is the same if the sides are changed. To prove it being associative, you can simply run through all possible combinations of having 3 bits being XOR-ed to each other, and the result will stay the same no matter what the order is.
Now, as we proved the above, let's see what happens if we XOR the same number at itself. Since the operation works on individual bits, we can test it on just two numbers: 0 and 1.
So, if you XOR a number onto itself, you always get 0 (believe it or not, but that property of XOR has been used by compilers, when a 0 needs to be loaded into a CPU register. It's faster to perform a bit operation than to explicitly push 0 into a register. The compiler will just produce assembly code to XOR a register onto itself).
Now, if X XOR X is 0, and XOR is associative, and you need to find out what number hasn't repeated in a sequence of numbers where all other numbers have been repeated two (or any other odd number of times). If we had the repeating numbers together, they will XOR to 0. Anything that is XOR-ed with 0 will remain itself. So, out of XOR-ing such a sequence, you will end up being left with a number that doesn't repeat (or repeats an even number of times).
这有很多通过位摆弄完成的各种功能的示例。其中一些可能非常复杂，所以要小心。
要理解位运算，您需要做的至少是：
对于 XOR，真值表很简单：
要获得结果中的位
n，请将规则应用于第一个和第二个输入中的位n。如果您尝试计算
1^1^0^1或任何其他组合，您会发现如果有奇数个 1，则结果为 1，否则为 0。您还会发现任何数字与自身进行异或运算都是 0，并且计算的顺序并不重要，例如1^1^(0^1) = 1^(1^0) ^1。这意味着，当您对列表中的所有数字进行异或时，重复（或出现偶数次）的数字将异或为 0，而您将只剩下出现奇数次的数字。
This has a lot of samples of various functionalities done by bit fiddling. Some of can be quite complex so beware.
What you need to do to understand the bit operations is, at least, this:
For XOR, the truth table is simple:
To obtain bit
nin the result you apply the rule to bitsnin the first and second inputs.If you try to calculate
1^1^0^1or any other combination, you will discover that the result is 1 if there is an odd number of 1's and 0 otherwise. You will also discover that any number XOR'ed with itself is 0 and that is doesn't matter in what order you do the calculations, e.g.1^1^(0^1) = 1^(1^0)^1.This means that when you XOR all the numbers in your list, the ones which are duplicates (or present an even number of times) will XOR to 0 and you will be left with just the one which is present an odd number of times.
从名称（按位）可以明显看出，它在位之间进行操作。
让我们看看它是如何工作的，
例如，我们有两个数字 a=3 和 b=4，
3 的二进制表示为 011，4 的二进制表示为 100，因此基本上相同位的异或结果为 0，相反位的异或结果为 1。
在给定的示例中，3^4（其中“^”是异或符号）将为我们提供 111，其十进制值为 7。
另一个例子，如果你给定一个数组，其中每个元素都出现两次，除了一个元素 &你必须找到那个元素。
你怎么能这么做呢？相同数字的简单异或将始终为 0，并且仅出现一次的数字将是您的输出。因为任何带有 0 的数字的输出都将是同名数字，因为该数字将具有零所没有的设置位。
As it is obvious from the name(bitwise), it operates between bits.
Let's see how it works,
for example, we have two numbers a=3 and b=4,
the binary representation of 3 is 011 and of 4 is 100, so basically xor of the same bits is 0 and for opposite bits, it is 1.
In the given example 3^4, where "^" is a xor symbol, will give us 111 whose decimal value will be 7.
for another example, if you've given an array in which every element occurs twice except one element & you've to find that element.
How can you do that? simple xor of the same numbers will always be 0 and the number which occur exactly once will be your output. because the output of any one number with 0 will be the same name number because the number will have set bits which zero don't have.