Parity of a number
Roger
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");
Joona I Palaste
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
Kevin Handy
>
> 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;
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--
Morris Dovey
> 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
Morris Dovey
> 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!
Joona I Palaste
> Kevin Handy wrote:
>> 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
Morris Dovey
> 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.
Kevin Handy
>
> Morris Dovey <mrd...@iedu.com> scribbled the following:
> > Kevin Handy wrote:
>
> >> 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
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.
Peter Nilsson
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
Tim Sweeney
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
Morris Dovey
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!
Dave Vandervies
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
Joona I Palaste
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
Gunnar Andersson
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
Manish Jethani
"Peter Nilsson" <ai...@acay.com.au> wrote in message
news:63f490f7.01110...@posting.google.com...
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
Peter Nilsson
>>
>> uint16_t p = i;
>>
>> p ^= p >> 8;
>> p ^= p >> 4;
>> p ^= p >> 2;
>> p ^= p >> 1;
>> p &= 1;
>>
>> Which I believe is O(1)!
>
>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?
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
Peter Nilsson
> #define logical_int_bit_size \
> (CHAR_BIT * sizeof(int))
Should be physical_int_bit_size of course!
--
Peter
Ian Woods
news:9s9mtq$pjc$3...@oravannahka.helsinki.fi:
> 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------
Ian Woods
news:Pine.GSO.4.31.011107...@my.nada.kth.se:
> 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. :)
Tim Sweeney
> about a worst-case complexity of Theta(n) for the parity of an n-bit
>
> int uint16_parity( uint16 x ) {
> x = x ^ (x >> 8);
> x = x ^ (x >> 4);
> x = x ^ (x >> 2);
> x = x ^ (x >> 1);
> return x & 1;
> }
Gunnar,
Thanks for the correction. I should've known better than to post a
piece of code without testing it. :-)
-Tim
Yaniv Sapir
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.
Tor Rustad
> k=0;
> while(d16)
> {
> k++;
> d16 &= (d16 - 1);
> }
>
> which will only loop for the number of on-bits.
On two's complement machines.
--
Tor <torust AT online DOT no>
Ben Pfaff
> "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
Tor Rustad
> "Tor Rustad" <tor...@online.no.spam> writes:
>
> > On two's complement machines.
>
> d16 was declared above as an unsigned type, so where does the
> kind of machine come into play?
I missed that d16 was declared as unsigned (in another post than the one I
replied to).
Michael Core
> > 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.
Tor Rustad
>
> (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.
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).