How to calculate parity using xor

Question

say we have this number 101001110110010 is this the correct way to calculate the parity using XOR:

10 10 01 11 01 10 01 0
1 1 1 0 1 1 1 0
0 1 0 1
1 1
0

I don't understand the problem so far. To check the whole number parity just check the lsb bit if its 1 its odd. — Take_Care_, Apr 10 '18 at 21:27
And another tip : XOR is commonly used to build parity generator. https://forum.allaboutcircuits.com/threads/xor-parity-generator.84919/ — Take_Care_, Apr 10 '18 at 21:37
Do you mean determine whether the number of ones is odd or even, in order to add a parity bit for error detection? — Arndt Jonasson, Apr 10 '18 at 22:10
You would use xor to compare two numbers, not reduce a string of bits to a single bit ... E.g. 11110000 ^ 00111100 = 11001100 — Kris, Apr 10 '18 at 21:27
xor can also be used to calculate the parity of a number by doing B1xorB2 ... in case of 2-bit numbers ... I'm trying to figure out how to do it for n bit numbers ... and if this is the correct way — Mohamed Benkedadra, Apr 10 '18 at 21:37

score 1 · Accepted Answer · answered Apr 20 '18 at 05:34

1

As an alternative to XORing every bit one by one, we can rely on the ability of a computer to XOR larger integers together. The parity of a large number that consists of two halves H and L, can be computed as the parity of H^L. That definition gives a (tail)recursive algorithm which halves the size the number at every step, and thus has a logarithmic call depth. It can be implemented iteratively, for example:

def parity(x):
    shiftamount = 1
    while x >> shiftamount:
        x ^= x >> shiftamount
        shiftamount <<= 1
    return x & 1

answered Apr 20 '18 at 05:34

harold

61,398
6
86
164

Can you provide an explanation about why this works? i.e. why does the parity of a large number hinge on the parity of H^L? – GuyPaddock Apr 18 '20 at 17:43
@GuyPaddock it doesn't necessarily hinge on H^L, that is just one choice for how to arrange the calculation - it's a very free choice because XOR is associative and commutative. This choice is convenient for implementation in Python (where there is more emphasis on pushing computation out of your own code, since Python is slow but its internal functions are not), but other arrangements make sense in other contexts (for example if you have access to the 32bit or 64bit limbs of a bigint, it makes more sense to first XOR those) – harold Apr 19 '20 at 13:36
1

Also see this explanation, which made the most sense to me: https://stackoverflow.com/a/21618038/4342230 – GuyPaddock Apr 20 '20 at 13:33

Mohamed Benkedadra · Answer 2 · 2018-04-20T05:20:00.180

i ended up answering my own question, this method is in fact correct, and i'm using it in a linear cryptanalysis implementation in python.

basically, to calculate the parity of a number using XOR, just take each couple of 2 bits and Xor them together, keep doing that until you're left with one number.

here's the implementation if you need it

def FindParity(value):
    parity = 0
    while value > 0:
        extractedValue =  value % 2
        value //= 2
        parity = parity ^ extractedValue

    return parity

this function just takes a number and does what i'm doing manually in my question.

How to calculate parity using xor

2 Answers2