2

What does ^= do in python?

I'm uncertain of whether ^ and ^= are similar or related in their name or behavior.

Example question:

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

nums = [3,3,4,2,2]

def singleNumber(self, nums: List[int]) -> int:
        a = 0
        for i in nums:
            a ^= i
        return a

I expect the output to be 4 in this case. But I have yet to find any definitive resource explaining how the ^= operator works.

Please explain what it is & how it works.

Community
  • 1
  • 1
MrFun
  • 2,303
  • 1
  • 15
  • 16
  • http://stackoverflow.com/questions/2451386, it's also listed with the other operators [in the docs](https://docs.python.org/3/reference/expressions.html#binary-bitwise-operations). – jonrsharpe Jul 05 '19 at 21:16
  • 2
    `a ^= i` is equivalent to `a = a ^ i` – Mark Jul 05 '19 at 21:16
  • 2
    Possible duplicate of [What does the caret operator (^) in Python do?](https://stackoverflow.com/questions/2451386/what-does-the-caret-operator-in-python-do) – abdusco Jul 05 '19 at 21:17
  • That seem to be leetcode problem? – sashaaero Jul 05 '19 at 21:21
  • I'd suggest leaving this question as there is substantial precedence for not merging questions about these types of operators into the base operator questions. https://stackoverflow.com/questions/823561/what-does-mean-in-python/823878 – MrFun Jul 05 '19 at 21:33

2 Answers2

3

The ^ operator is a binary XOR (exclusive OR). So ^= is an XOR of i over a, placed back in a.

for example: 

a  = 9 1001
a ^= 5 0101
       ----
   XOR 1100 = 12

a will contain 12

For the list [3,3,4,2,2]:

a  = 0 000
a ^= 3 011 -> 011
a ^= 3        011 -> 000
a ^= 4               100 -> 100
a ^= 2                      010 -> 110
a ^= 2                             010 -> 100 = 4
Alain T.
  • 40,517
  • 4
  • 31
  • 51
2

If you are interested in how the algorithm actually works, it depends on the unwanted elements to be pairs - specifically an even number of them. Using XOR, you can do things like:

>>> A ^ A
 0
>>> B == A ^ B ^ A
 True

for any integer values of A and B. I.e. an XOR of something with itself is zero, A ^ A is zero. Similarly a number XOR zero is itself, like A ^ 0 is A. The operation is also commutative, so A ^ A ^ B (which reduces to 0 ^ B which is simply B) is the same as A ^ B ^ A. So if you apply this to a list where all but one element appears an even number of times, the only the odd one out remains when they are all XOR'd together.

As for the ^= operator, that is explained already. A ^= B is the same as A = A ^ B. Many operators can be used this way, e.g. A += 1 is the same as A = A + 1.

Deepstop
  • 3,627
  • 2
  • 8
  • 21