CODEWITHSUNDEEP
pythonoperators
MrFun
MrFun

Reputation: 2588

What does "^=" mean in Python?

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.

Upvotes: 2

Views: 1131

Answers (2)

Alain T.
Alain T.

Reputation: 42143

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

Upvotes: 3

Deepstop
Deepstop

Reputation: 3807

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.

Upvotes: 2

Related Questions