How can I check if a value has even parity of bits or odd?

by 
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;

Assuming you know ints are 32 bits.

Let’s see how this works. To keep it simple, let’s use an 8 bit integer, for which we can skip the first two shift/XORs. Let’s label the bits a through h. If we look at our number we see:

( a b c d e f g h )

The first operation is x ^= x >> 4 (remember we’re skipping the first two operations since we’re only dealing with an 8-bit integer in this example). Let’s write the new values of each bit by combining the letters that are XOR’d together (for example, ab means the bit has the value a xor b).

( a b c d e f g h )
xor
( 0 0 0 0 a b c d )

The result is the following bits:

( a b c d ae bf cg dh )

The next operation is x ^= x >> 2:

( a b c d ae bf cg dh )
xor
( 0 0 a b c d ae bf )

The result is the following bits:

( a b ac bd ace bdf aceg bdfh )

Notice how we are beginning to accumulate all the bits on the right-hand side.

The next operation is x ^= x >> 1:

( a b ac bd ace bdf aceg bdfh )
xor
( 0 a b ac bd ace bdf aceg )

The result is the following bits:

( a ab abc abcd abcde abcdef abcdefg abcdefgh )

We have accumulated all the bits in the original word, XOR’d together, in the least-significant bit. So this bit is now zero if and only if there were an even number of 1 bits in the input word (even parity). The same process works on 32-bit integers (but requires those two additional shifts that we skipped in this demonstration).

The final line of code simply strips off all but the least-significant bit (& 1) and then flips it (~x). The result, then, is 1 if the parity of the input word was even, or zero otherwise.

More Related Contents:

  1. Is CHAR_BIT ever > 8?
  2. Order of fields when using a bit field in C
  3. Logic behind sizeof operator [duplicate]
  4. How to Implement stack by function pointer and how to use it [closed]
  5. Minimize a linear programming system in C
  6. I got an unknown error on my coding for a C program [closed]
  7. Are all data pointers the same size in one platform for all data types? [duplicate]
  8. Order of local variable allocation on the stack
  9. Why is “a” != “a” in C?
  10. getch and arrow codes
  11. What is the meaning of lines starting with a hash sign and number like ‘# 1 “a.c”‘ in the gcc preprocessor output?
  12. Is unsigned integer subtraction defined behavior?
  13. Segmentation Fault, large arrays
  14. Why can’t I convert ‘char**’ to a ‘const char* const*’ in C?
  15. How do I execute an external program within C code in Linux with arguments?
  16. stdout thread-safe in C on Linux?
  17. What does ‘sizeof (function name)’ return?
  18. How to do unsigned saturating addition in C?
  19. Switch statement: must default be the last case?
  20. What are the differences between poll and select?
  21. Left-pad printf with spaces
  22. Mis-aligned pointers on x86
  23. Sizeof arrays and pointers
  24. Very fast memcpy for image processing?
  25. C syntax for functions returning function pointers
  26. realloc(): invalid next size when reallocating to make space for strcat on char * [duplicate]
  27. C code with undefined results, compiler generates invalid code (with -O3)
  28. What’s the difference between “int” and “int_fast16_t”?
  29. Is there any option to switch between C99 and C11 C standards in Visual Studio?
  30. How to read terminal’s input buffer immediately after keypress

Leave a Comment