evenly divides the code is simpler than if we werefor exampleto use bit subwords we illustrate the approach with lookup table for -bit words the cache is --these are the parities of ( )( )( )( )respectively to compute the parity of ( we would compute the parities of ( )( )( )( by table lookup we see these are respectivelyso the final result is the parity of which is to lookup the parity of the first two bits in ( )we right shift by to get ( )and use this as an index into the cache to lookup the parity of the next two bitsi ( )we right shift by to get ( in the two least-significant bit places the right shift does not remove the leading ( )--it results in ( we cannot index the cache with thisit leads to an out-of-bounds access to get the last two bits after the right shift by we bitwise-and ( with ( (this is the "maskused to extract the last bitsthe result is ( similar masking is needed for the two other -bit lookups def parity ( )mask_size bit_mask xffff return precomputed_parity [ >( mask_size )precomputed_parity [( >( mask_size )bit_mask precomputed_parity [( >mask_size bit_mask precomputed_parity [ bit_mask ]the time complexity is function of the size of the keys used to index the lookup table let be the width of the words for which we cache the resultsand the word size since there are / termsthe time complexity is ( / )assuming word-level operationssuch as shiftingtake ( time (this does not include the time for initialization of the lookup table we can improve on the (nworst-case time complexity of the previous algorithms by exploiting some simple properties of parity specificallythe xor of two bits is defined to be if both bits are or both bits are otherwise it is xor has the property of being associativei it does not matter how we group bitsas well as commutativei the order in which we perform the xors does not change the result the xor of group of bits is its parity we can exploit this fact to use the cpu' word-level xor instruction to process multiple bits at time for examplethe parity of hb equals the parity of the xor of hb and hb the xor of these two -bit values can be computed with single shift and single -bit xor instruction we repeat the same operation on - - - - -and -bit operands to get the final result note that the leading bits are not meaningfuland we have to explicitly extract the result from the least-significant bit we illustrate the approach with an -bit word the parity of ( is the same as the parity of ( xored with ( ) of ( this in turn is the same as the parity of ( xored with ( ) of ( the final result is the xor of ( with ( ) note that the first xor yields ( )and only the last bits are relevant going forward the second xor yields ( )and only the last bits are relevant the third xor yields ( the last bit is the resultand to extract it we have to bitwise-and with ( def parity ( ) ^ > ^ >