CODEWITHSUNDEEP
cbit-manipulationbitxor
user2517777
user2517777

Reputation: 751

What is an XOR sum?

I am not sure of the precise definition of this term.

I know that a bitwise XOR operation is going bit by bit and taking the XOR of corresponding bits position wise. Is this result termed the 'XOR sum'? If not, what is an XOR sum, and how do you use XOR to implement this addition?

Upvotes: 37

Views: 55545

Answers (1)

haccks
haccks

Reputation: 106012

In a bit wise XOR operation:

a   b   a^b
-----------
0   0    0
0   1    1
1   0    1
1   1    0

XOR sum refers to successive XOR operations on integers.
Suppose you have numbers from 1 to N and you have to find their XOR sum, then for N = 6, XOR sum will be 1^2^3^4^5^6 = 7.

1 = 001,  2 = 010,   3 = 011,   4 = 100,   5 = 101,   6 = 110  

 1^2          = 1^2  = 001^010 = 011 = 3  
(1^2)^3       = 3^3  = 011^011 = 000 = 0
(1^2^3)^4     = 0^4  = 000^100 = 100 = 4
(1^2^3^4)^5   = 4^5  = 100^101 = 001 = 1
(1^2^3^4^5)^6 = 1^6  = 001^110 = 111 = 7 --> XOR sum

Tips:

Remember these basic rules of XOR operation while doing XOR sum:

  • 0^a = a (e.g. 0^3 = 3)
  • a^a = 0 (e.g. 3^3 = 0)
  • XOR operations are cumutative (swapping doesn't matter). a^b = b^a
  • XOR operations are assosiative (grouping doesn't matter). (a^b^c) = (a^b)^c = a^(b^c)

Examples with application of above rules:

  • 1^2^1 = (1^1)^2 = 0^2 = 2
  • (1^2^1) ^ (1^2) = (1^2)^(1^2) ^ 1 = 0^1 = 1

Hope this will help.

Upvotes: 64

Related Questions