Algorithm Bit Algorithms: C Programming Coding

Write a C program to find the parity of an unsigned integer

Write a C program to find parity of an unsigned integer - Bit Algorithm - Parity of a number refers to whether it contains an odd or even number of 1-bit

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

 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


C Programming
# include <stdio.h>
# define  bool int
/* Function to get parity of number n. It returns 1
   if n has odd parity, and returns 0 if n has even
   parity */
bool getParity(unsigned int n)
    bool parity = 0;
    while (n)
        parity = !parity;
        n      = n & (n - 1);
    return parity;
/* Driver program to test getParity() */
int main()
    unsigned int n = 7;
    printf("Parity of no %d = %s",  n, 
             (getParity(n)? "odd": "even"));
    return 0;

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.

See also  Branch and Bound | Set 1 (Introduction with 0/1 Knapsack)

About the author

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment