return result the time complexity is ( )where is the word size we will now describe several algorithms for parity computation that are superior to the bruteforce algorithm the first improvement is based on erasing the lowest set bit in word in single operationthereby improving performance in the bestand average-cases specificallythe expression ~( )where is the bitwise-and operator and is the bitwise complement operator the variable is at exactly the lowest bit of that is all other bits in are for exampleif ( ) then ( ) ~( ( ) and ( ) ( ) ( ) this calculation is robust--it is correct for unsigned and two' -complement representations consequentlythis bit may be removed from by computing ywhere is the bitwise-xor function the time complexity is ( )where is the number of bits set to in def parity ( )result while xresult ^ & drops the lowest set bit of return result let be the number of bits set to in particular word (for examplefor then time complexity of the algorithm above is (kthe fact that ~( isolates the lowest bit that is in is important enough that you should memorize it howeverit is also fairly easy to derive firstsuppose is not it has has bit that is one subtracting one from changes the rightmost bit to zero and sets all the lower bits to one (if you add one nowyou get the original value backthe effect is to mask out the rightmost one therefore ~( has single bit set to onenamelythe rightmost in now suppose is subtracting one from underflowsresulting in word in which all bits are set to one againx ~( is similar derivation shows that &( replaces the lowest bit that is with for exampleif ( ) then ( ) so &( ( ) &( ) ( ) this fact can also be very useful we now consider qualitatively different approach the problem statement refers to computing the parity for very large number of words when you have to perform large number of parity computationsandmore generallyany kind of bit fiddling computationstwo keys to performance are processing multiple bits at time and caching results in an array-based lookup table first we demonstrate caching clearlywe cannot cache the parity of every -bit integer--we would need bits of storagewhich is of the order of ten trillion exabytes howeverwhen computing the parity of collection of bitsit does not matter how we group those bitsi the computation is associative thereforewe can compute the parity of -bit integer by grouping its bits into four nonoverlapping bit subwordscomputing the parity of each subwordsand then computing the parity of these four subresults we choose since is relatively small