Ch4, Q4.1 Parity of a word. Confusion with the O(logn) solution of splitting bits into half

#1

I am not sure if I understand the O(logn) solution of this question.

def parity(x):

Let’s say, parity of 8 (or 1000). After the operation in the book that goes splitting the bit into half at every step:

x^=x>>2

what I don’t specifically understand is this part in the book(EPI in python pg 29, 2018 edition) using a similar example with an 8-bit number 11010111, paraphrasing it kind of:
“Note that the first XOR yields 11011010, and only last 4 digits are relevant going forward”.

Why is that? How come only last 4 digits are relevant?

Can some please explain me the logic behind that. Thanks so much in advance.

0 Likes
#2

Hi @geekidharsh,

I am following the Java version of the book, but I think it doesn’t matter.

Actually, the answer lies in the upper paragraphs.

XOR has associative and commutative properties. In the solution, these properties are exploited to use CPU’s XOR instructions to process multiple bits. That is, it doesn’t matter how we group the bits or the order of XOR operations.

The XOR of a group of bits is its parity.

The parity of <b63, b62, ..., b2, b1, b0> equals the parity of the XOR of <b63, b62, ..., b32> and <b31, b30, ..., b0>.

In order to have <b31, b30, ..., b0> you need to apply right shift by 32. And, to calculate the result’s parity, again you need to consider the above definition. Thus, the parity of <b31, b30, ..., b0> equals the parity of the XOR of <b31, b30, ..., b16> and <b15, b14, ..., b0>. This needs to be repeated on 8-, 4-, 2-, and 1-bit operands to get the final result. Each time, we reduce the number of bits. Finally, the last bit is the result so we can bitwise-AND to extract the parity information.

Hope this helps!

0 Likes