XOR code to find smallest B for which A+B=A^B
Here we will learn to work with the properties of XOR operation in Python with an easy example.
XOR GATE in Python
The XOR operation basically outputs 1 if the inputs (binary) are different and 0 otherwise. For more clear understanding you can refer to this link for the truth table for two bits. The binary exclusive-or operation has two inputs and one output.
The second property and the main property for this question is that the XOR operation never produces carry. Hence using this property we can easily figure out the logic for the question.
The XOR Algorithm/Logic
The naive approach to this question is to find the value starting from 0 to n-1 and check for which number A+B=A^B. This will take a lot of time (O(n) where n is the number from 0 to the number input by the user, which is not good for competitive coding) if the number is in order of 109 . to come up with the optimized approach and solution we have to understand the properties and apply them efficiently.
To find the minimum number such that A+B=A^B we have to find find the position of the first bit which is 0 in the input A from the right side(indexing from 0). After we get this position we perform 2^count to get the minimum value of B. If we don’t get the first 0 we return A+1. Take a look at the example below:
A=8(binary->1000) first zero is at position 0 so count=0 B=2^count=1(required answer) A=7(binary->111) first zero is not there so we return A+1 =8
Python Code: XOR code to find the smallest B for which A+B=A^B
Now the code in python3. Before looking at the code try it yourself.
import math A=int(input()) copy=A #to create a copy of input count=-1 flag=0 while(A!=0): if(A%2==0): #to count the first occurence of zero from right in binary count+=1 flag=1 break A=A//2 count+=1 if(flag==1): print("B=",int(math.pow(2,count))) else: print("B=",copy+1)
Thank you for reading. I hope you understood the logic, for any queries comment below. Keep coding! coders.