deepwork's blog

By deepwork, history, 23 months ago, ,

Question is solved, please ignore this post

Why if xor sum of segment is equal to sum of segment, this condition is also satisfied for all subsegments of original segment?
I know that it's true when all bits in numbers are unique, but is it the only case when it's true, and if it is, then why?

• +5

 » 23 months ago, # |   +1 Think about the binary representation of the bits. How is it possible that the xor sum is equal to the sum? If you figure that out, then it is obvious that this also holds for all subsegments.
•  » » 23 months ago, # ^ |   +1 My friend told me that it's satisfied when all bits are unique. Yes that makes sense and it's true. But is it the only case when xorsum is equal to sum?
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +5 Yes, of course. Assume that two numbers have the same bits set. Then in the xor sum these bits vaporize . And in the sum they add up 2i + 2i = 2i + 1. So if any bits are equal, then then the xor sum is guaranteed smaller than the sum.
•  » » » » 23 months ago, # ^ |   +1 Thank You very much, great explanation!
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   +15 I'd also like to add that the there's a relation between the functions sum & xor & andThat is sum(a, b) = xor(a, b) + 2 * and(a, b)if looked closely at what Jakube said, if a = b then their xor would be 0 and all the bits that are both set (i.e. equals 1) in the binary representation of a, b that the xor function ignored because xor(1, 1) = 0 are accounted for by the and function because and(1, 1) = 1 and thus this value is shifted to the left by 1 bit (that is they get multiplied by 2)Hope this helps you visualize what's going on.
•  » » » » » 23 months ago, # ^ |   +4 OMG, I'm blown away, thank You!World of bits is so amazing!
•  » » » » » » 23 months ago, # ^ |   +7 You're welcome :)Here's a practice problem for that 635C - XOR Equation
•  » » » » » » » 23 months ago, # ^ |   +3 Thank You :)
 » 23 months ago, # |   0 Auto comment: topic has been updated by ROIgold (previous revision, new revision, compare).