# Byte parity question...

Discussion in 'C Programming' started by philbo30, Sep 10, 2007.

1. ### philbo30Guest

I admit, I didn't spend any time researching this yet so this is the
first step...

Is there a C function available to determine byte parity or is the
usual course to just count the 1s?

philbo30, Sep 10, 2007

2. ### cr88192Guest

"philbo30" <> wrote in message
news:...
>I admit, I didn't spend any time researching this yet so this is the
> first step...
>
> Is there a C function available to determine byte parity or is the
> usual course to just count the 1s?
>

counting 1s, though possible, but is a slow option.

k=0; for(j=0; j<8; j++)if(i&(1<<j))k++;
even: !(k&1)
odd: k&1

one can use a table, or a bitmap, instead.

nibbles (Even, Odd):
0-E 1-O 2-O 3-E
4-O 5-E 6-E 7-O
8-O 9-E A-E B-O
C-E D-O E-O F-E

static int p_even=0x9669;
static int p_odd=0x6996;

nibble 'i' is even? 'p_even&(1<<i)' or '(p_even>>i)&1'.

and for a byte:
((p_even>>(i&15))&1)==((p_even>>((i>>4)&15))&1)

or, odd:
((p_odd>>(i&15))^(p_odd>>((i>>4)&15)))&1

consequently, we can define a bitmap table, and do a byte like this:
(p_even_bm[i>>4]>>(i&15))&1
(p_odd_bm[i>>4]>>(i&15))&1

or, even faster (but taking a lot more space), is giving an individual value
for every input value:
p_even_tab
p_odd_tab

along with other possibilities...

cr88192, Sep 10, 2007

3. ### Guest

On Sep 10, 4:13 am, philbo30 <> wrote:
> I admit, I didn't spend any time researching this yet so this is the
> first step...
>
> Is there a C function available to determine byte parity or is the
> usual course to just count the 1s?

You may use XOR operation.

, Sep 10, 2007
4. ### Charlie GordonGuest

<> a écrit dans le message de news:
...
> On Sep 10, 4:13 am, philbo30 <> wrote:
>> I admit, I didn't spend any time researching this yet so this is the
>> first step...
>>
>> Is there a C function available to determine byte parity or is the
>> usual course to just count the 1s?

>
> You may use XOR operation.

That's an interesting alternative to a memory based lookup table.
Assuming bytes have 8 bits, this code should do:

static inline int byte_parity(unsigned char b) {
b ^= b >> 4;
b ^= b >> 2;
b ^= b >> 1;
return b & 1;
}

This method can be easily generalized to larger unsigned types.

--
Chqrlie

Charlie Gordon, Sep 10, 2007

philbo30 wrote:
> I admit, I didn't spend any time researching this yet so this is the
> first step...
>
> Is there a C function available to determine byte parity or is the
> usual course to just count the 1s?

There is no such function in the standard C library.

If CHAR_BIT is 8, you could use this table:

static unsigned char parity[] =
{
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,
1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,
1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,
0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,
1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,
0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,
0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,
0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,
1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,
0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,
0,1,0,1,1,0
};

where parity[octet] gives the bit count. Yes, the above table was
generated by simply counting the 1s.

--
Tor <torust [at] online [dot] no>

> where parity[octet] gives the bit count.

ITYM:

"where parity[octet] gives the parity of the octet."

--
Tor <torust [at] online [dot] no>

7. ### Richard TobinGuest

In article <>,

>> where parity[octet] gives the bit count.

>ITYM:
>
>"where parity[octet] gives the parity of the octet."

Maybe he just forgot to say "modulo 2" at the end.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

Richard Tobin, Sep 10, 2007

Charlie Gordon wrote:
> <> a écrit dans le message de news:
> ...
>> On Sep 10, 4:13 am, philbo30 <> wrote:

>>> Is there a C function available to determine byte parity or is the
>>> usual course to just count the 1s?

>
> Assuming bytes have 8 bits, this code should do:
>
> static inline int byte_parity(unsigned char b) {
> b ^= b >> 4;
> b ^= b >> 2;
> b ^= b >> 1;
> return b & 1;
> }
>
> This method can be easily generalized to larger unsigned types.

This generalization, for a byte, should work for all sizes of bytes.
Most compilers will eliminate the while loop for 8-bit byte targets.

/* Function: parity
** Description: Return the parity of the argument.
*/
int /* parity of b: 1 if number of 1 bits is odd,
** 0 otherwise. */
parity (unsigned char b) {
while (b > 0xff) {
b = (b >> 8) ^ (b & 0xff);
}
b ^= b >> 4;
b ^= b >> 2;
return ((b >> 1) ^ b) & 1;
}

--

9. ### Michal NazarewiczGuest

>> On Sep 10, 4:13 am, philbo30 <> wrote:
>>> Is there a C function available to determine byte parity or is the
>>> usual course to just count the 1s?

> Charlie Gordon wrote:
>> Assuming bytes have 8 bits, this code should do:
>>
>> static inline int byte_parity(unsigned char b) {
>> b ^= b >> 4;
>> b ^= b >> 2;
>> b ^= b >> 1;
>> return b & 1;
>> }
>>
>> This method can be easily generalized to larger unsigned types.

> This generalization, for a byte, should work for all sizes of
> bytes. Most compilers will eliminate the while loop for 8-bit byte
> targets.

Or one could use preprocessor directives to help compiler a bit:

> /* Function: parity
> ** Description: Return the parity of the argument.
> */
> int /* parity of b: 1 if number of 1 bits is odd,
> ** 0 otherwise. */
> parity (unsigned char b) {

#if CHAR_BIT > 16
> while (b > 0xff) {
> b = (b >> 8) ^ (b & 0xff);
> }

#elif CHAR_BIT > 8
b ^= b >> 8;
#endif
> b ^= b >> 4;
> b ^= b >> 2;
> return ((b >> 1) ^ b) & 1;
> }

--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86*tlen.pl>---<jid:mina86*chrome.pl>--ooO--(_)--Ooo--

Michal Nazarewicz, Sep 11, 2007