473,322 Members | 1,714 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Parity check of a word

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
Nov 15 '05 #1
15 23563
In article <pa****************************@localhost.localdom ain>,
Herbert Haas <hh@localhost.localdomain> wrote:
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.
--
"Who Leads?" / "The men who must... driven men, compelled men."
"Freak men."
"You're all freaks, sir. But you always have been freaks.
Life is a freak. That's its hope and glory." -- Alfred Bester, TSMD
Nov 15 '05 #2
Herbert Haas <hh@localhost.localdomain> writes:
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;
}
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Nov 15 '05 #3

"Herbert Haas" <hh@localhost.localdomain> wrote in message
news:pa****************************@localhost.loca ldomain...
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
Nov 15 '05 #4
Mike Wahler wrote:
"Herbert Haas" <hh@localhost.localdomain> wrote in message
news:pa****************************@localhost.loca ldomain...
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;
}

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Nov 15 '05 #5
Ben Pfaff wrote:
/* 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.

Nov 15 '05 #6

ke******@hotmail.com wrote:
Ben Pfaff wrote:
/* 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.


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

Nov 15 '05 #7
ke******@hotmail.com wrote
(in article
<11**********************@g43g2000cwa.googlegroups .com>):
Ben Pfaff wrote:
/* 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.


Try changing the last line to return x & 1;

?

--
Randy Howard (2reply remove FOOBAR)

Nov 15 '05 #8
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.

Nov 15 '05 #9
ke******@hotmail.com wrote
(in article
<11**********************@o13g2000cwo.googlegroups .com>):
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.

--
Randy Howard (2reply remove FOOBAR)

Nov 15 '05 #10
Randy Howard wrote:
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

Nov 15 '05 #11

bq****@gmail.com wrote:
what is that 'H.D.' ?


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

Nov 15 '05 #12
bq****@gmail.com wrote
(in article
<11**********************@o13g2000cwo.googlegroups .com>):
Randy Howard wrote:
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)


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.
--
Randy Howard (2reply remove FOOBAR)

Nov 15 '05 #13
Randy, thank you for your advice.

Nov 15 '05 #14
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
Nov 15 '05 #15

Lawrence Kirby wrote:
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


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

Krishanu

Nov 15 '05 #16

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Aaron | last post by:
DOes anyone know how to check the length of words in a string? I want all the word in a string to be less than 100 char to prevent buffer overflow. Thanks. Aaron
5
by: Ken JS | last post by:
How do I find the Parity Check Matrix, when I’m given the generator matrix? e.g. | 1 0 0 1 1 | G = | 0 1 0 1 2 | | 0 0 1 1 3 | Can anybody teach me how to find the Parity Check...
1
by: santel | last post by:
Hi, How to check whether the MSOffice files like word, excel, powerpoint are installed in the machine or not? Anyone please help!
1
by: poreko | last post by:
hi guys! does anyone know why the LSB (less significant bit) of the codeword is always used as the parity bit.
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.