**Theory:**

- The parity of a word is 1 if the number of 1s in the word is odd; otherwise, it is 0. For example, the parity of 1011 is 1, and the parity of 10001000 is 0.
- Parity check are used to detect single bit errors in data storage and comminucation
- Trick must know: x&(x-1) equals with x with its lowest set bit erased. Example:

Given n = 845, in binary = 1101001101, n – 1 in binary = 1101001100, and n after n&(n-1) in binary = 1101001100. Continue, n after n&(n-1) in binary yields 1101001000, then 1101000000, so on. Until n becomes zero.

**Solutions:**

def parity(n):
result = 0
while n:
result ^= (n & 1)
n >>= 1
return result

The brute force algorithm iteratively tests the value of each bit while tracking the number of 1s seen so far.

First, we initialize result = 0, while n is still not 0, result is updated by applying the ^ (xor) operator on the returned value when we check if the least significant bit of n is 1 or 0. More explanation, value of result first is 0, so if there is 3 1s in n, result will be 1 (value of result is 1 or 0 each while-loop). n >>= 1 right shifts n 1 bit, eventually n will reach 0.

Time complexity: **O(n)** with n is number of bits of the given number.

Do you notice in the theory section above, the trick can be applied here to shorten the running time of the brute force solution. This is true because number of 1s equals with number of the lowest set bit. The change is minor:

def parity_improved(n):
result = 0
while n:
result ^= 1
n &= n-1
return result

Time complexity: O(k), with k is the number of lowest set bit.

**Different approaches. **

The problem statement refers to computing the parity for a very large number of words. When you have to perform a large number of parity computations, more generally, any kind of bit fiddling computations, two keys to performance are processing multiple bits at a time and caching results in an array-based lookup table.

Clearly, we cannot cache the parity of every 64-bit integer, we would need pow(2,64) bits of storage, which is of the order of two exabytes. However, when computing the parity of a collection of bits, it does not matter how we group those bits, the computation is associative. Therefor, we can compute the parity of a 64-bit integer by grouping its bits into four non-overlapping 16 bit subwords, computing the parity of each subwords and then computing the parity of these four subresults. We choose 16 since pow(2, 16) is relatively small, which makes it feasible to cache the parity of all 16-bit words using an array. Furthermore, since 16 evenly divides 64.

Example with a lookup table for 2-bit words. The cache is [0, 1, 1, 0], these are parities of [00, 01, 10, 11], respectively. To compute parity of 11001010, we would compute the parities of 11, 00, 10, 10. By table lookup, we see these are 0,0,1,1, respectively, so the final result is 0.

To lookup the parity of the first two bits in 11101010, we right shift by 6, to get 00000011, and use this as an index into the cache. To lookup the parity of the next two bits 10, we right shift by 4. However, right shift does not remove the leading 11 when we right shift by 4 – results in 00001110. To get the last two bits after the right shift by 4, we bitwise-AND 00001110 with 00000011 (the “mask” to extract the last 2 bits). The result is 00000010. Similar masking needed fir the two other 2-bit lookups.

Given PRECOMPUTED_PARITIES is an array of parities of all numbers from 0 up to 65535. The code is fairly understandable.

def parity_caching(n):
MASK_SIZE = 16
BIT_MASK = 0XFFFF
# first right shift 48 to get first 16 bits
# then righ shift 32 to get next 16 bits
# then right shift 16 to get next 16 bits
# final and with BIT_MASK to get the final 16 bits
# and xor all of them together to get final result
return (PRECOMPUTED_PARITIES[n >> (3 * MASK_SIZE)] ^
PRECOMPUTED_PARITIES[(n >> (2 * MASK_SIZE)) & BIT_MASK] ^
PRECOMPUTED_PARITIES[(n >> MASK_SIZE) & BIT_MASK] ^
PRECOMPUTED_PARITIES[n & BIT_MASK])

Time complexity: O(n/L), with L is the width we cache the results.

XOR has the property of being associative, it does not matter how we group bits, as well as commutative, the order in which we perform the XORs does not change result. The **XOR of a group of bits is its parity**. For example, the parity of [b63,b62,…,b2,b1,b0] equals the parity of the XOR of [b63,b62,..b32] and [b31,b30,..,b2,b1]. The XOR of these two 32-bit values can be computed with a single shift and a single 32-bit XOR instruction. We repeat the same operation on 32-, 16-, 8-, 4-, 2- and 1-but operands to get the final result. Note that the leading bits are not meaningful, and we have to explicitly extract the result from the least-significant bit.

Example with an 8-bit word. The parity of 11010111 is the asme as the parity of 1101 XOR with 0111 – results in 1010. This in turn is the same as the parity of 10 XOR with 10 – results in 00. The final result of 0 XOR with 0 is 0. Note that the first XOR yields 11011010 and only the last 4 bits are relevant going forward. The second XOR yields 11101100, and only the last 2 bits are relevant. The third XOR yields 10011010. The last bit is the result, and to extract it we have to bitwise AND with 00000001. The code:

def parity_property(n):
x ^= x >> 32
x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1
return x & 0x1

Time complexity: O(logn)

## Reply