Categories
algorithms kotlin

Problem 5.1 from EPI -> Compute parity of a word

The solution I present here is not a complete solution, in the book there is log(n) solution which exploits the 32 bit CPU xor and shift operation. Here I am implemented the second best option which has a time complexity of (N/L), n is the word size while l is the cache size. The trick to this solution is to use a mask which can help you to extract bits, once that is done use a cache which will have an index and a value, value will be the parity of that index. While we are calculating the cache we also calculate the parity in a variable called result. Take a look at the solution here.

Leave a Reply

Your email address will not be published. Required fields are marked *