A value has even parity if it has an even number of 1 bits. A value has an odd parity if it has an odd number of 1 bits. For example, 0110 has even parity, and 1110 has odd parity.
I have to return 1 if x has even parity.
int has_even_parity(unsigned int x) {
return
}
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.
GCC has built-in functions for this:
Built-in Function:
int __builtin_parity (unsigned int x)Returns the parity of
x, i.e. the number of 1-bits in x modulo 2.
and similar functions for unsigned long and unsigned long long.
I.e. this function behaves like has_odd_parity. Invert the value for has_even_parity.
These should be the fastest alternative on GCC. Of course its use is not portable as such, but you can use it in your implementation, guarded by a macro for example.
The following answer was unashamedly lifted directly from Bit Twiddling Hacks By Sean Eron Anderson, seander@cs.stanford.edu
Compute parity of word with a multiply
The following method computes the parity of the 32-bit value in only 8 operations >using a multiply.
unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;
Also for 64-bits, 8 operations are still enough.
unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;
Andrew Shapira came up with this and sent it to me on Sept. 2, 2007.
Try:
int has_even_parity(unsigned int x){
unsigned int count = 0, i, b = 1;
for(i = 0; i < 32; i++){
if( x & (b << i) ){count++;}
}
if( (count % 2) ){return 0;}
return 1;
}
valter
To generalise @TypelA's answer for any architecture:
int has_even_parity(unsigned int x)
{
unsigned char shift=1;
while (shift < (sizeof(x)*8))
{
x ^= (x>>shift);
shift<<=1;
}
return !(x & 0x1);
}
The main idea is this. Unset the rightmost '1' bit by using x & ( x - 1 ). Lets say x = 13(1101) and the operation of x & ( x - 1 ) is 1101 & 1100 which is 1100, notice that the rightmost set bit is converted to 0.
Now x is 1100. The operation of x & ( x - 1 ) i.e 1100 & 1011 is 1000. Notice that the original x is 1101 and after two operations of x & (x - 1) the x is 1000, i.e two set bits are removed after two operations. If after odd number of operations, the x becomes zero, then its a odd parity, else its a even parity.
Here's a one line #define that does the trick for a char:
#define PARITY(x) ((~(x ^= (x ^= (x ^= x >> 4) >> 2) >> 1)) & 1) /* even parity */
int main()
{
char x=3;
printf("parity = %d\n", PARITY(x));
}
It's portable as heck and easily modified to work with bigger words (16, 32 bit). It's important to note also, using a #define speeds the code up, each function call requires time to push the stack and allocate memory. Code size doesn't suffer, especially if it's implemented only a few times in your code - the function call might take up as much object code as the XORs.
Admittedly, the same efficiencies may be obtained by using the inline function version of this, inline char parity(char x) {return PARITY(x);} (GCC) or __inline char parity(char x) {return PARITY(x);} (MSVC). Presuming you keep the one line define.
int parity_check(unsigned x) {
int parity = 0;
while(x != 0) {
parity ^= x;
x >>= 1;
}
return (parity & 0x1);
}
This is quite an old question but I'm posting this for whoever might use it in the future.
I won't add an example of doing it in c since there are enough good answers already.
In case the end result is supposed to be a piece of code that can work (be compiled) with a c program then I suggest the following:
.code
; bool CheckParity(size_t Result)
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
END
This is a piece of code I'm using to check the parity of calculated results in a 64bit c program compiled using MSVC. You can obviously port it to 32bit or other compilers.
This has the advantage of being much faster than using c and it also leverages the cpus functionality.
What this example does is take as input a parameter (passed in RCX - __fastcall calling convention). It increments it by 0 thus setting the cpus Parity Flag and then setting a variable (RAX) to 0 or 1 if Parity Flag is on or not.
