We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Sum vs XOR
- Discussions
Sum vs XOR
Sum vs XOR
Sort by
recency
|
114 Discussions
|
Please Login in order to post a comment
Java
Python 3
This problem can be solved by counting the no. of 0s in n's binary form, and return 2 raise to the power (no. of 0s). Whenever we add any two binary numbers and get any carry, that numbers don't satisfy the equation n+x = n^x. But the positions in n where we have 0s, there we can place any of one from 0 or 1. that means if there is one 0 in binary n then we have two choices to place a number at that position in x, that number can be either 0 or 1 (means 2^1 choices). If a has 2 0s then 2^2 choices. For 3, 2^3 choices and so on. So we have 2^(no. of 0s in n's binary form) choices. But also keep in mind the case when n is 0, then return 1.
This principle also works for other bases like decimal, octal. E.g. if we have 20 of base 10 then we have 10^1 choices to place a number at the position of 0, the numbers are from 0-9. Same for octal too.
def sumXor(n):
Python 3
C#
zeros in binary form of n acts as an exponent for 2 to find number of possible values that in an XOR statement with n, retains n's positive bits and their own positive bits.