Parity: Parity of a number refers to whether it contains an odd or even number of 1-bits. The number has “odd parity”, if it contains odd number of 1-bits and is “even parity” if it contains even number of 1-bits.
Main idea of the below solution is – Loop while n is not 0 and in loop unset one of the set bits and invert parity.
Algorithm: getParity(n)
1. Initialize parity = 0
2. Loop while n != 0
a. Invert parity
parity = !parity
b. Unset rightmost set bit
n = n & (n-1)
3. return parity
Example:
Initialize: n = 13 (1101) parity = 0
n = 13 & 12 = 12 (1100) parity = 1
n = 12 & 11 = 8 (1000) parity = 0
n = 8 & 7 = 0 (0000) parity = 1
Program:
[pastacode lang=”c” manual=”%23%20include%20%3Cstdio.h%3E%0A%23%20define%20%20bool%20int%0A%20%0A%2F*%20Function%20to%20get%20parity%20of%20number%20n.%20It%20returns%201%0A%20%20%20if%20n%20has%20odd%20parity%2C%20and%20returns%200%20if%20n%20has%20even%0A%20%20%20parity%20*%2F%0Abool%20getParity(unsigned%20int%20n)%0A%7B%0A%20%20%20%20bool%20parity%20%3D%200%3B%0A%20%20%20%20while%20(n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20parity%20%3D%20!parity%3B%0A%20%20%20%20%20%20%20%20n%20%20%20%20%20%20%3D%20n%20%26%20(n%20-%201)%3B%0A%20%20%20%20%7D%20%20%20%20%20%20%20%20%0A%20%20%20%20return%20parity%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20getParity()%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20unsigned%20int%20n%20%3D%207%3B%0A%20%20%20%20printf(%22Parity%20of%20no%20%25d%20%3D%20%25s%22%2C%20%20n%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20(getParity(n)%3F%20%22odd%22%3A%20%22even%22))%3B%0A%20%20%20%20%20%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C Programming” highlight=”” provider=”manual”/]Above solution can be optimized by using lookup table. Please refer to Bit Twiddle Hacks[1st reference] for details.
Time Complexity: The time taken by above algorithm is proportional to the number of bits set. Worst case complexity is O(Logn).
Uses: Parity is used in error detection and cryptography.
[ad type=”banner”]