+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: XOR solution explanation needed. (/thread-30541.html)
XOR solution explanation needed. - omm - Oct-25-2020
Question:
For a given list of numbers, only one digit is repeated odd number of times. Pass the list through function and return the number which is repeated odd number of times.
I have a solution for it. But, I found another solution by other user which I did not understand. Here is the code
def find_it(seq):
result = 0
for x in seq:
result ^= x
return result
find_it([1,2,3,1,2,3,1])XOR seems to be implemented but, how is the only odd number being detected.More explanation:
I have tried printing the binary values of result and x before and after statement result ^= x to understand what is happening but, could not.
Any other resources that you can point me to get better understanding?
For value 1 , Before ^x Operation. bin(result) = 0b0 , bin(x) = 0b1 For value 1 , After ^x Operation. bin(result) = 0b1 , bin(x) = 0b1 Result = 1 For value 2 , Before ^x Operation. bin(result) = 0b1 , bin(x) = 0b10 For value 2 , After ^x Operation. bin(result) = 0b11 , bin(x) = 0b10 Result = 3 For value 3 , Before ^x Operation. bin(result) = 0b11 , bin(x) = 0b11 For value 3 , After ^x Operation. bin(result) = 0b0 , bin(x) = 0b11 Result = 0 For value 1 , Before ^x Operation. bin(result) = 0b0 , bin(x) = 0b1 For value 1 , After ^x Operation. bin(result) = 0b1 , bin(x) = 0b1 Result = 1 For value 2 , Before ^x Operation. bin(result) = 0b1 , bin(x) = 0b10 For value 2 , After ^x Operation. bin(result) = 0b11 , bin(x) = 0b10 Result = 3 For value 3 , Before ^x Operation. bin(result) = 0b11 , bin(x) = 0b11 For value 3 , After ^x Operation. bin(result) = 0b0 , bin(x) = 0b11 Result = 0 For value 1 , Before ^x Operation. bin(result) = 0b0 , bin(x) = 0b1 For value 1 , After ^x Operation. bin(result) = 0b1 , bin(x) = 0b1 Result = 1 For value 4 , Before ^x Operation. bin(result) = 0b1 , bin(x) = 0b100 For value 4 , After ^x Operation. bin(result) = 0b101 , bin(x) = 0b100 Result = 5 For value 4 , Before ^x Operation. bin(result) = 0b101 , bin(x) = 0b100 For value 4 , After ^x Operation. bin(result) = 0b1 , bin(x) = 0b100 Result = 1 1 Process finished with exit code 0Thanks,
Om
RE: XOR solution explanation needed. - buran - Oct-25-2020
Couple of observations:
1. Your assignment states that in the sequence only one number is odd. In the code you pass sequence with multiple odd numbers.
2. If you pass different sequence, result is not as expected.
e.g.
print(find_it([2,3,1,2,3,1]))
Output:0RE: XOR solution explanation needed. - omm - Oct-25-2020
(Oct-25-2020, 06:30 AM)omm Wrote: Question:
For a given list of numbers, only one digit is repeated odd number of times. Pass the list through function and return the number which is repeated odd number of times.
Sorry for the confusion. I did not write the question right earlier and I have corrected now. It has to return the only number which is repeated odd number of times (need not be an odd number). Example: [3,2,3,2,2]. Here, 2 is repeated 3 times and we need to return the number 2.
Thanks.
RE: XOR solution explanation needed. - buran - Oct-25-2020
Please, don't edit post after you get reply. Now my post does not correspond to the content of your post.
RE: XOR solution explanation needed. - omm - Oct-25-2020
(Oct-25-2020, 09:21 AM)buran Wrote: Please, don't edit post after you get reply. Now my post does not correspond to the content of your post.
Got it. Would never repeat it.
RE: XOR solution explanation needed. - jefsummers - Oct-25-2020
A number, XOR'd with itself, will be 0. So, each digit, if present an even number of times, wipes itself out to 0. If an odd number of times then one time will be left (if present 7 times, the first 6 xor to 0, then 0 xor the digit is the digit).
RE: XOR solution explanation needed. - deanhystad - Oct-26-2020
A number XOR itself is zero, and a number XOR with zero is the number.
3 ^ 3 == 0 and 3 ^ 0 == 3, therefore (3 ^ 3) ^ 3 == 3.
If we sort the numbers and put them in groups:
[1,2,3,1,2,3,1] == [1,1,1,2,2,3,3] == [[1,1,1], [2,2], [3,3]]
It should be easy to see that.
1^1^1 == (1^1)^1 == 0^1 == 1
2^2 == 0
3^3 == 0
And that:
(1^0)^0 == 1^0 == 1
Another way to think about this is to group numbers into pairs knowing that the XOR
of each pair is zero:
1,2,3,1,2,3,1] = [1,1,1,2,2,3,3] = [[1,1], [1], [2,2], [3,3]] == [0, 1, 0, 0]
(0^1)^(0^0) == 1^0 == 1
The pairs cancel each other out!
But does this hold true if the numbers are placed in a different order? Think of the bits as a row of switches. All switches start off (0). When you XOR a number you toggle the switches associated with the bits that are set (1) in the number.
Output:switch Number
0000 0110 0^6 = 6
0110 0011 (0^6)^3 = 5
0101 0110 ((6^2)^3)^6) = 3
0011
flipped 0231This is bad code. It is certainly clever, and it does a good job starting a conversation about XOR and maybe leading to deeper understanding, but it is bad code. Good code requires thinking to write, but once written it should be very easy to understand.
This code is also bad because it is not flexible. This code only works if there is one number in the list that appears an odd number of times. This same logic cannot be used as the foundation for a function that returns a list of all numbers that appear in a list an odd number of times.
Finally this code is bad because it quietly gives a bad result if the list does not meet all the requirements. Look what happens if if there are more than one number that appears an odd number of times:
[1,1,2,2,2,3,3,3] == [[1,1],[2,2],[2],[3,3],[3]] == [0,0,2,0,3] == 2^3 == 1 # What?
If there is supposed to only be one number that appears an odd number of times and two or more numbers appearing and odd number of times is an error, I would prefer the code raises an exception instead of giving me a nonsensical number.
RE: XOR solution explanation needed. - omm - Oct-26-2020
Thanks for the clear and elaborate explanation.
(Oct-26-2020, 04:09 AM)deanhystad Wrote: A number XOR itself is zero, and a number XOR with zero is the number.
3 ^ 3 == 0 and 3 ^ 0 == 3, therefore (3 ^ 3) ^ 3 == 3.
If we sort the numbers and put them in groups:
[1,2,3,1,2,3,1] == [1,1,1,2,2,3,3] == [[1,1,1], [2,2], [3,3]]
It should be easy to see that.
1^1^1 == (1^1)^1 == 0^1 == 1
2^2 == 0
3^3 == 0
And that:
(1^0)^0 == 1^0 == 1
Another way to think about this is to group numbers into pairs knowing that the XOR
of each pair is zero:
1,2,3,1,2,3,1] = [1,1,1,2,2,3,3] = [[1,1], [1], [2,2], [3,3]] == [0, 1, 0, 0]
(0^1)^(0^0) == 1^0 == 1
The pairs cancel each other out!
But does this hold true if the numbers are placed in a different order? Think of the bits as a row of switches. All switches start off (0). When you XOR a number you toggle the switches associated with the bits that are set (1) in the number.
The switches that are flipped an odd number of times end up being on (1), and the switches flipped an even number of times end up being off (0). Looking at the example it should be obvious that the order of the numbers does not affect how many times each switch is flipped.
This is bad code. It is certainly clever, and it does a good job starting a conversation about XOR and maybe leading to deeper understanding, but it is bad code. Good code requires thinking to write, but once written it should be very easy to understand.
This code is also bad because it is not flexible. This code only works if there is one number in the list that appears an odd number of times. This same logic cannot be used as the foundation for a function that returns a list of all numbers that appear in a list an odd number of times.
Finally this code is bad because it quietly gives a bad result if the list does not meet all the requirements. Look what happens if if there are more than one number that appears an odd number of times:
[1,1,2,2,2,3,3,3] == [[1,1],[2,2],[2],[3,3],[3]] == [0,0,2,0,3] == 2^3 == 1 # What?
If there is supposed to only be one number that appears an odd number of times and two or more numbers appearing and odd number of times is an error, I would prefer the code raises an exception instead of giving me a nonsensical number.