deepwork's blog

By deepwork, history, 23 months ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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   Vote: I like it +5 Vote: I do not like it

      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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thank You very much, great explanation!

      • »
        »
        »
        »
        23 months ago, # ^ |
        Rev. 2   Vote: I like it +15 Vote: I do not like it

        I'd also like to add that the there's a relation between the functions sum & xor & and

        That 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, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ROIgold (previous revision, new revision, compare).