Parity check of a word

[Herbert Haas]

Hi everyone,

is there a simple and fast method to check the parity of a word (e. g. a
4-byte integer)? That is I want to know whether the number of ones are
even or odd.

Of course I could do that with some extra code, but I guess there should
be at least an ASM command? (Intel)

Thanks for any help!

Regards
Herbert

 

[Ben Pfaff]

is there a simple and fast method to check the parity of a word (e. g. a
4-byte integer)? That is I want to know whether the number of ones are
even or odd.

Based on code from the book _Hacker's Delight_ (any errors are
mine):

/* Returns parity of X. */
int parity (unsigned x)
{
x ^= x >> 1;
x ^= x >> 2;
x ^= x >> 4;
x ^= x >> 8;
x ^= x >> 16;
return x;
}

 

[Walter Roberson]

is there a simple and fast method to check the parity of a word (e. g. a
4-byte integer)? That is I want to know whether the number of ones are
even or odd.

Of course I could do that with some extra code, but I guess there should
be at least an ASM command? (Intel)

Machine level or assembler capabilities are beyond the scope
of comp.lang.c .

"Simple and fast"... there's always look-up tables and small loops.

 

[Mike Wahler]

Hi everyone,

is there a simple and fast method to check the parity of a word (e. g. a
4-byte integer)? That is I want to know whether the number of ones are
even or odd.

Of course I could do that with some extra code, but I guess there should
be at least an ASM command? (Intel)

We only discuss standard C here, not assembly language.

Here's a simple example in C:

#include <limits.h>
#include <stdio.h>

unsigned int bits(unsigned int value)
{
unsigned int result = 0;

unsigned int mask = 1;

while(mask)
{
result += (value & mask) != 0;
mask *= 2;
}

return result;
}

unsigned int even(unsigned int value)
{
return !(bits(value) % 2);
}

unsigned int odd(unsigned int value)
{
return !even(value);
}

int main()
{
const char *parity[] = {"ODD", "EVEN"};
unsigned int i = 0;

puts("Value Bits Parity");

for(; i < 20; ++i)
printf("%5u %4u %s\n", i, bits(i), parity[even(i)]);

return 0;
}

Note that the above method will only work for unsigned values.

-Mike

 

[Joe Wright]

Hi everyone,

is there a simple and fast method to check the parity of a word (e. g. a
4-byte integer)? That is I want to know whether the number of ones are
even or odd.

Of course I could do that with some extra code, but I guess there should
be at least an ASM command? (Intel)

We only discuss standard C here, not assembly language.

Here's a simple example in C:

#include <limits.h>
#include <stdio.h>

unsigned int bits(unsigned int value)
{
unsigned int result = 0;

unsigned int mask = 1;

while(mask)
{
result += (value & mask) != 0;
mask *= 2;
}

return result;
}

unsigned int even(unsigned int value)
{
return !(bits(value) % 2);
}

unsigned int odd(unsigned int value)
{
return !even(value);
}

int main()
{
const char *parity[] = {"ODD", "EVEN"};
unsigned int i = 0;

puts("Value Bits Parity");

for(; i < 20; ++i)
printf("%5u %4u %s\n", i, bits(i), parity[even(i)]);

return 0;
}

Note that the above method will only work for unsigned values.

-Mike

Consider..

int bits(unsigned i) {
int n = 0;
while (i) {
i &= i-1;
++n;
}
return n;
}

 

[kernelxu]

/* Returns parity of X. */
int parity (unsigned x)
{
x ^= x >> 1;
> x ^= x >> 2;
> x ^= x >> 4;
x ^= x >> 8;
> x ^= x >> 16;
return x;

}

hi, I'm afraid it doesn't work.

 

[Krishanu Debnath]

hi, I'm afraid it doesn't work.

Following code works for even parity scheme.

int parity (unsigned x)
{
unsigned y;

y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >>16);
return y & 1;
}

Krishanu

 

[Randy Howard]

(e-mail address removed) wrote
(in article

hi, I'm afraid it doesn't work.

Try changing the last line to return x & 1;

?

 

[kernelxu]

Randy Howard's advice:
/* Returns parity of X. */
int parity1(int data)
{
data ^= (data >> 1);
data ^= (data >> 2);
data ^= (data >> 4);
data ^= (data >> 8);
data ^= (data >> 16);
return (data & 0x1);
}
and
Krishanu Debnath's advice:
int parity2(unsigned x)
{
unsigned int data;

data = x ^(x >> 1);
data ^= (data >> 2);
data ^= (data >> 4);
data ^= (data >> 8);
data ^= (data >> 16);
return (data & 1);
}
they are both working very well.
Thank you!
returning 1 means the parity is ODD,while returning 0 means the parity
is EVEN.
I found the idea was too odd to understand, could any body explain it
in details.
thanks in advance.

 

[Randy Howard]

(e-mail address removed) wrote
(in article

Randy Howard's advice:
/* Returns parity of X. */
int parity1(int data)
{
data ^= (data >> 1);
data ^= (data >> 2);
data ^= (data >> 4);
data ^= (data >> 8);
data ^= (data >> 16);
return (data & 0x1);
}

[snip another /very/ similar solution]

they are both working very well.
Thank you!

No problem, I suspect that Ben just forgot to read the paragraph
under the code fragment on page 75 of H.D. when he put it in the
form of a function.

returning 1 means the parity is ODD,while returning 0 means the parity
is EVEN.
I found the idea was too odd to understand, could any body explain it
in details.

For stuff like this, watching it is better than explaining. You
could work it out by hand with some sample values. That is
usually the best way to make the lightbulb come on.

Or, you could simply insert a bunch of printf() statements in
between the lines of code above so you can see the intermediate
results, then call it with some example values for 'data' and
have the computer do the work for you, but show the steps on the
way to the answer.

If you pick good sample values, you should see a pattern emerge
quickly.

 

[bqbert]

No problem, I suspect that Ben just forgot to read the paragraph
under the code fragment on page 75 of H.D. when he put it in the
form of a function.

what is that 'H.D.' ?
I once devised a similar hack, but I did things in the reverse order
(>>16, 8, etc)

thanks

 

[bqbert]

what is that 'H.D.' ?

Ah, sorry for the noise (I just re-read the thread)

 

[Randy Howard]

(e-mail address removed) wrote
(in article

what is that 'H.D.' ?
I once devised a similar hack, but I did things in the reverse order
(>>16, 8, etc)

Sorry, Ben quoted it upthread, so I let it go. Hacker's
Delight, (which is about the real use of the word 'hacker' not
the one that has been invented by the media), by Henry S.
Warren, Jr. A very interesting read, particularly if you work
on low-level bit twiddling or anything performance-critical.
It's also interesting in that it isn't aimed at the "All the
world's an Intel x86" crowd for a change.

 

[kernelxu]

Randy, thank you for your advice.

 

[Lawrence Kirby]

On Mon, 29 Aug 2005 01:37:27 -0700, Krishanu Debnath wrote:

....

Following code works for even parity scheme.

int parity (unsigned x)
{
unsigned y;

y = x ^ (x >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >>16);
return y & 1;
}

However it assumes that int/unsigned int are wider than 16 bits
which is not portable; if unsigned is 16 bits wide then y >> 16 has
undefined behaviour. If you want an unsigned type can can store at least
32 bits use unsigned long, or maybe uint_least32_t in C99.

Lawrence

 

[Krishanu Debnath]

On Mon, 29 Aug 2005 01:37:27 -0700, Krishanu Debnath wrote:

...


However it assumes that int/unsigned int are wider than 16 bits
which is not portable; if unsigned is 16 bits wide then y >> 16 has
undefined behaviour. If you want an unsigned type can can store at least

Yes, that is true. But OP specifically mentioned that he needs it for
4-byte
integer.

Krishanu