uint16_t d16; /* 16 bit unsigned int */
uint16_t j;
int i, k;
/* find parity of d16 */
d16 = 0x03;
j = 1; k = 0;
for (i = 0; i < 16; i++)
{
if (j & d16)
k++;
j = j << 1;
}
if (k % 2)
printf("Even parity");
else
printf("Odd parity");
There isn't really a much more efficient algorithm than what you're
already doing. No matter what your algorithm looks like, to calculate
the parity you have to AND your number with every power of two your
int type holds. You can fine-tune your algorithm with some clever
micro-optimisation, but that usually is more work than it's worth.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Nothing lasts forever - so why not destroy it now?"
- Quake
If you don't mind mangling d16
k=0;
while(d16)
{
k++;
d16 &= (d16 - 1);
}
which will only loop for the number of on-bits.
Speed: Depends on your processor, but might be slightly faster,
depending speed of operations.
--cut this code out--
> j = 1; k = 0;
> for (i = 0; i < 16; i++)
> {
> if (j & d16)
> k++;
> j = j << 1;
> }
--end cut--
> How to find the odd parity of an integer?
> I have this code, but is there any simpler method?
>
> uint16_t d16; /* 16 bit unsigned int */
> uint16_t j;
> int i, k;
>
> /* find parity of d16 */
> d16 = 0x03;
> j = 1; k = 0;
> for (i = 0; i < 16; i++)
> {
> if (j & d16)
> k++;
> j = j << 1;
> }
>
> if (k % 2)
> printf("Even parity");
> else
> printf("Odd parity");
Roger...
Does this qualify as simpler?
/* returns 0 if even; 1 if odd */
unsigned parity(unsigned v)
{ unsigned bits = 0;
while (v)
{ bits += (v & 1);
v >>= 1;
}
return bits & 1;
}
--
Morris Dovey
West Des Moines, Iowa USA
> If you don't mind mangling d16
>
> k=0;
> while(d16)
> {
> k++;
> d16 &= (d16 - 1);
> }
>
> which will only loop for the number of on-bits.
Kevin...
Very nice!
>> If you don't mind mangling d16
>>
>> k=0;
>> while(d16)
>> {
>> k++;
>> d16 &= (d16 - 1);
>> }
>>
>> which will only loop for the number of on-bits.
> Kevin...
> Very nice!
Even with this algorithm, the original value of d16 can be preserved by
some trivial assignments to temporary variables. On a big enough int
size (something like 256 or 1024 or 4096 bits...) the overhead of
performing the two or three assignments required is lost among the
performance gain in the loop, because stuff inside the loop is O(n),
while stuff outside the loop is O(1).
Implementing the trivial assignments is left as an exercise for the
reader.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Hasta la Vista, Abie!"
- Bart Simpson
> Even with this algorithm, the original value of d16 can be preserved by
> some trivial assignments to temporary variables. On a big enough int
> size (something like 256 or 1024 or 4096 bits...) the overhead of
> performing the two or three assignments required is lost among the
> performance gain in the loop, because stuff inside the loop is O(n),
> while stuff outside the loop is O(1).
Joona...
Right! I've already stuffed it into my utility library over on my Linux
partition. By implementing it as a function I disposed of worries about
resetting the original value.
Left as an exercise. Just trying to give the algorythm in the
simplest form, and minimizing variable usage.
> size (something like 256 or 1024 or 4096 bits...) the overhead of
> performing the two or three assignments required is lost among the
> performance gain in the loop, because stuff inside the loop is O(n),
> while stuff outside the loop is O(1).
> Implementing the trivial assignments is left as an exercise for the
> reader.
Remember to only use unsigned int's for this formula. A signed
int may get you into trouble.
Since your size appears to be known:
uint16_t p = i;
p ^= p >> 8;
p ^= p >> 4;
p ^= p >> 2;
p ^= p >> 1;
p &= 1;
Which I believe is O(1)!
I can't remember where I saw it first. Probably the same place I saw
the "Butterfly Shift".
--
Peter
uint16_t d;
uint16_t t0,t1,t2,t3;
int parity;
t0=d^(d>>8);
t1=d^(d>>4);
t2=d^(d>>2);
t3=d^(d>>1);
parity=t3&1;
-Tim
Tim...
Aw, c'mon yourself! ;-)
Any idea why an equivalent coding wouldn't be:
uint16 d, parity;
parity = (d^(d>>1)) & 1;
which would only calculate parity over the low-order two bits!
It helps, though, if you get the _right_ xors and shifts; your code
will return the parity of the last two bits of d, which I suspect is
not what you intended.
dave
--
Dave Vandervies dj3v...@student.math.uwaterloo.ca
> really, get a grip.
I already have a handle -- karl_m if you please.
--Mark McIntyre and Karl Malbrain in comp.lang.c
Take another look at your code. You don't use t0, t1 or t2 anywhere.
Your whole code is equivalent to:
uint16_t d;
int parity;
parity=(d^(d>>1))&1;
which calculates a parity bit for the last two bits in d. The values of
the left-most (CHAR_BIT-2) bits are irrelevant.
--
/-- Joona Palaste (pal...@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"You have moved your mouse, for these changes to take effect you must shut down
and restart your computer. Do you want to restart your computer now?"
- Karri Kalpio
On 7 Nov 2001, Joona I Palaste wrote:
> Take another look at your code. You don't use t0, t1 or t2 anywhere.
> Your whole code is equivalent to:
>
> uint16_t d;
> int parity;
> parity=(d^(d>>1))&1;
>
> which calculates a parity bit for the last two bits in d. The values of
> the left-most (CHAR_BIT-2) bits are irrelevant.
His code is wrong but his statement is right, and your statement
about a worst-case complexity of Theta(n) for the parity of an n-bit
number if wrong. Consider the following code:
int uint16_parity( uint16 x ) {
x = x ^ (x >> 8);
x = x ^ (x >> 4);
x = x ^ (x >> 2);
x = x ^ (x >> 1);
return x & 1;
}
By adding one more line, the parity of a 32-bit number is computed,
and by adding two more lines, the parity of a 64-bit number is
computed.
If this code is critical for performance, as it is in some
applications, I think the last three lines beginning with "x ="
should be replaced by the table lookup
x = parity_of_eight_bit_number[x];
/ Gunnar
So even if the size is not known, should this be the best way to
do it?
/* 0: even; 1: odd; */
int parity(unsigned num)
{
int p = num;
size_t s = sizeof(num) * CHAR_BIT;
while(s /= 2) p ^= (p >> s);
return (p & 1);
}
??? Right?
Manish
Not quite! :)
If you want to be completely general, then you have to initialise s to be
the minimum power of two greater or equal to the bit size of int.
Forget about p and use unsigned int because right shifting is well defined
for that type.
When we all start working on 16385-bit machines the following code will
break...
#define logical_int_bit_size \
(CHAR_BIT * sizeof(int))
#define weasible_int_bit_size \
( logical_int_bit_size > 8192 ? 16384 \
: logical_int_bit_size > 4096 ? 8192 \
: logical_int_bit_size > 2048 ? 4096 \
: logical_int_bit_size > 1024 ? 2048 \
: logical_int_bit_size > 512 ? 1024 \
: logical_int_bit_size > 256 ? 512 \
: logical_int_bit_size > 128 ? 256 \
: logical_int_bit_size > 64 ? 128 \
: logical_int_bit_size > 32 ? 64 \
: logical_int_bit_size > 16 ? 32 \
: 16 )
int parity(unsigned int num) {
int s = (int) weasible_int_bit_size / 2;
do {
num ^= num >> s;
} while (s /= 2);
return (int) (num & 1U);
}
But in practice, this technique is likely to be slower than optimised
bit-counting if the sample ints have statistically few ones, e.g. simple
ascii text. But I say this in light of the fact that the performance of the
various methods is _very_ platform dependant.
--
Peter
Should be physical_int_bit_size of course!
--
Peter
> Roger <ar...@lycos.com> scribbled the following:
>> Hi all,
>> How to find the odd parity of an integer?
>> I have this code, but is there any simpler method?
>> Thank You.
>
>> uint16_t d16; /* 16 bit unsigned int */
>> uint16_t j;
>> int i, k;
>
>> /* find parity of d16 */
>> d16 = 0x03;
>> j = 1; k = 0;
>> for (i = 0; i < 16; i++)
>> {
>> if (j & d16)
>> k++;
>> j = j << 1;
>> }
>
>> if (k % 2)
>> printf("Even parity"); else printf("Odd parity");
>
> There isn't really a much more efficient algorithm than what you're
> already doing. No matter what your algorithm looks like, to calculate
> the parity you have to AND your number with every power of two your
> int type holds. You can fine-tune your algorithm with some clever
> micro-optimisation, but that usually is more work than it's worth.
>
i=i^(i>>1);
i=i^(i>>2);
i=i^(i>>4);
i=i^(i>>8);
i=i&1;
can be used to calculate the parity of an unsigned 16 bit number. You need
log2(n) shifts and exclusive-or operations (that is, keep adding lines
doubling the number of the shift each time up to half of the word size).
The performance gain for a single 16 bit value is small - but when you're
doing a few hundred thousand a second it adds up! :)
Ian Woods
--
to email me, change the email address in the obvious way.
http://www.geekcode.com
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS\E\S D- S-:+(+) A-- C+++(+) UL++++ P(+) L+++>++++ E--- W++ N++ a+ K- w--
-(+++++) V- PS+ PE-(--) Y+ PGP(+) t 5++ X- R+(++) (!)tv-- b++(+)
DI(+) D++() G+ e++>++++ h-(+)>--- r--- y--(**)
------END GEEK CODE BLOCK------
> If this code is critical for performance, as it is in some
> applications, I think the last three lines beginning with "x ="
> should be replaced by the table lookup
>
> x = parity_of_eight_bit_number[x];
>
>
> / Gunnar
>
>
I'd expect this to be slower on many architectures - afterall, calculating
it in the first place only takes a handful of operations for an 8 bit
number (3 shifts and exclusive ors), whereas setting up and performing the
table lookup could easily be more.
In order to say which would be faster, one must always look to what happens
in the real world on a real piece of hardware on the right day, at the
right time and with the wind blowing in the right direction. :)
Gunnar,
Thanks for the correction. I should've known better than to post a
piece of code without testing it. :-)
-Tim
Don't know about general purpose CPU's, but at least in the DSP's I know,
there is an instruction for one's population count in a register, so it may
be preferable to use this instruction in an asm{} statement, for speed
optimization.
Yaniv.
On two's complement machines.
--
Tor <torust AT online DOT no>
> "Kevin Handy" <k...@srv.net> wrote in message
>
> > k=0;
> > while(d16)
> > {
> > k++;
> > d16 &= (d16 - 1);
> > }
> >
> > which will only loop for the number of on-bits.
>
> On two's complement machines.
d16 was declared above as an unsigned type, so where does the
kind of machine come into play?
--
"Large amounts of money tend to quench any scruples I might be having."
-- Stephan Wilms
I missed that d16 was declared as unsigned (in another post than the one I
replied to).
> > k=0;
> > while(d16)
> > {
> > k++;
> > d16 &= (d16 - 1);
> > }
> >
> > which will only loop for the number of on-bits.
(Without an instruction-set supporting parity information,) the fastest way is
IMHO using a lookup-table. Save the parity for all values between 0 and x in
this table. E.G. on a 32-bit machine you would normally store for all values
between 0 and 255. You perform 4 shift operations and lookup every 8 bits
separately. Of course, aslong as you know the target platform, you can use much
better improvements. Saving the parity for all values between 0 and 65535 takes
only 8 * 8192 bits and you would have to shift only twice. If you don't fear
using assembler... OK, that OT.
Using a lookup table might be faster, or it might very well not be. When
accessing data far apart, this may cause cache misses (which are quite
expensive).