bit operations and parity

[Lew]

He did say ASCII.

And ASCII has the data in the low 7 bit.

I understand, but the trouble when you assume ...

I agree that it is likely that the high bit is for parity, but I cannot be
certain, which is why I asked the OP which bit is used for parity. I note
that they have not yet been pleased to answer that question.

Either way, the point of the answers we've all given has been to show how the
calculations might be done, be the high bit or the low one for parity.

I had an interview once where the interviewer posed a problem. They posited a
file containing English words where each letter was assigned a monetary value:
a penny for "A", two cents for "B, "and so on," they told me. I asked how
much "C" was worth. "Just continue the series," they responded, seeming
nonplused that I should ask. "Sure," I said, "but is it '1, 2, 3, 4, 5, ...',
'1, 2, 4, 8, 16, ...', '1, 2, 3, 5, 8, 13, 21, ...'?"

It helps to make specifications explicit.

PS: Or should we call it US-ASCII ...

The Americas comprise more than the United States.

 

[Mayeul]

Not quite direct, but:

boolean evenParity =
((Integer.bitCount( theByte & 0xff ) & 0x01) == 0);

Thank you. Should have been looking at Integer methods first thing, what
was I thinking?

(There are also highestOneBit() and numberOfLeadingZeros() methods and
their equivalent at the other side, which would have saved me quite some
hassle if only I had looked for them.)

 

[Daniel Pitts]

Well it appears from what I can discern that if

if(((int)theParityInPlace % 2) == (int) theParityAsZeroOrOne)

then it is even parity and it passes -- if I understand what is going
on correctly.

Wrong, theParityInPlace is either 128 or 0, both %2 are 0.
theParityAsZeroOrOne is theParityInPlace /128, so it is either 1 or 0

*then*, to verify the *actual* parity of the data, you have to actually
*calculate* the parity. The only way to do that is add all the bits, and
then test whether that value is even or odd

Here is a shortcut for that test. It is an o(logn) algorithm, compared
to the o(n) algorithm you seem to be looking at.
byte s1 = (dataByte ^ (dataBase >> 4))
s1 ^= s1 >> 2;
s1 ^= s1 >> 1;
byte dataByteActualyParity = (s1 & 1);
if (dataByteActualyParity != theParityAsZeroOrOne) {
// Error, the parity check failed!
}

 

[Lew]

Wrong, theParityInPlace is either 128 or 0, both %2 are 0.
theParityAsZeroOrOne is theParityInPlace /128, so it is either 1 or 0

*then*, to verify the *actual* parity of the data, you have to actually
*calculate* the parity. The only way to do that is add all the bits, and
then test whether that value is even or odd

Here is a shortcut for that test. It is an o(logn) algorithm, compared
to the o(n) algorithm you seem to be looking at.
byte s1 = (dataByte ^ (dataBase >> 4))

^^^^ Byte

If dataByte < 0 the upper four bits will not be flipped.
If dataByte >= 0 the upper four bits will be flipped.

Does this matter?

 

[Lew]

     Don't you have "will" and "will not" reversed?

Actually, I had "<" and ">=" flipped. :0)

 

[Arne Vajhøj]

I understand, but the trouble when you assume ...

I agree that it is likely that the high bit is for parity, but I cannot
be certain, which is why I asked the OP which bit is used for parity. I
note that they have not yet been pleased to answer that question.

Either way, the point of the answers we've all given has been to show
how the calculations might be done, be the high bit or the low one for
parity.

I had an interview once where the interviewer posed a problem. They
posited a file containing English words where each letter was assigned a
monetary value: a penny for "A", two cents for "B, "and so on," they
told me. I asked how much "C" was worth. "Just continue the series,"
they responded, seeming nonplused that I should ask. "Sure," I said,
"but is it '1, 2, 3, 4, 5, ...', '1, 2, 4, 8, 16, ...', '1, 2, 3, 5, 8,
13, 21, ...'?"

It helps to make specifications explicit.
True.


The Americas comprise more than the United States.

That was a reference to another thread.

Arne

 

[Lew]

Lew:
Arne:
That was a reference to another thread.

Your remark was humorous in that context. I was following up on the concept
but I don't take the "ASCII" vs. "US-ASCII" controversy seriously. My
apologies - my attempt to join in your humor fell far flatter than your
comment did.

 

[Daniel Pitts]

^^^^ Byte

If dataByte < 0 the upper four bits will not be flipped.
If dataByte >= 0 the upper four bits will be flipped.

Does this matter?

Sign extension doesn't matter:
The algorithm basically combines the upper 4 bits with the lower 4
Then the upper 2 bits of the lower nibble with the lower 2 bites of
nibble (garbage can come in from the upper nibble, but that does not
affect the lower 2 bits)
Then the lowest two bits are xorred.

 

[Roedy Green]

To compute the parity of a byte, you can do

byte data = ...;
int parity = data ^ (data >> 4);
parity ^= parity >> 2;
parity ^= parity >> 1;
parity &= 1;

as an SSCCE

/*
* @(#)TestParity.java
*
* Summary: Detect if a byte has even or odd parity, i.e. even or odd
number of 1 bits.
*
* Copyright: (c) 2009 Roedy Green, Canadian Mind Products,
http://mindprod.com
*
* Licence: This software may be copied and used freely for any
purpose but military.
* http://mindprod.com/contact/nonmil.html
*
* Requires: JDK 1.6+
*
* Created with: IntelliJ IDEA IDE.
*
* Version History:
* 1.0 2009-07-29 - initial version
* 1.1 2009-08-03 - add Eric Sosman's xor method
*/
package com.mindprod.example;

import java.io.UnsupportedEncodingException;
import static java.lang.System.out;

/**
* Detect if a byte has even or odd parity, i.e. even or odd number of
1 bits.
*
* @author Roedy Green, Canadian Mind Products
* @version 1.1 2009-08-03 - add Eric Sosman's xor method
* @since 2009-07-29
*/
public final class TestParity
{
// -------------------------- PUBLIC STATIC METHODS
--------------------------

/**
* Calculate parity of a single byte
*
* @param b byte to test
*
* @return true of if odd parity, false if even parity
*/
public static boolean isOddParity( final byte b )
{
int bb = b;
int bitCount = 0;
// Process bits right to left, shifting each bit in turn into
the lsb position.
for ( int i = 0; i < 8; i++, bb >>>= 1 )
{
if ( ( bb & 1 ) != 0 )
{
bitCount++;
}
}
return ( bitCount & 1 ) != 0;
}

/**
* Calculate parity of a single byte, using Eric Sosman's xor
method
*
* @param b byte to test
*
* @return true of if odd parity, false if even parity
*/
public static boolean isOddParityViaSosman( final byte b )
{
final int bb = b & 0xff;
int parity = bb ^ ( bb >> 4 );
parity ^= parity >> 2;
parity ^= parity >> 1;
return ( parity & 1 ) != 0;
}

// --------------------------- main() method
---------------------------

/**
* Test harness
*
* @param args not used
*
* @throws java.io.UnsupportedEncodingException
* in case UTF-8 support missing.
*/
public static void main( String[] args ) throws
UnsupportedEncodingException
{
out.println( isOddParity( ( byte ) 0xff ) ); // false
out.println( isOddParity( ( byte ) 0x70 ) ); // true
out.println( isOddParityViaSosman( ( byte ) 0xff ) ); //
false
out.println( isOddParityViaSosman( ( byte ) 0x70 ) ); //
true
}
}
--
Roedy Green Canadian Mind Products
http://mindprod.com

"Patriotism is fierce as a fever, pitiless as the grave, blind as a stone, and as irrational as a headless hen."
~ Ambrose Bierce (born: 1842-06-24 died: 1914 at age: 71)

 

[Bill McCleary]

Sign extension doesn't matter:
The algorithm basically combines the upper 4 bits with the lower 4
Then the upper 2 bits of the lower nibble with the lower 2 bites of
nibble ...

Isn't the spelling "nybble"?

 

[Roedy Green]

byte data = ...;
int parity = data ^ (data >> 4);
parity ^= parity >> 2;
parity ^= parity >> 1;
parity &= 1;

the Intel machines compute the parity of the result of almost every
instruction as a side effect and poke it into the condition register.
This means they do it is less than a machine cycle.

I wonder what sort of hardware algorithm they use, perhaps a tree of
xor gates that work in parallel.
--
Roedy Green Canadian Mind Products
http://mindprod.com

"Patriotism is fierce as a fever, pitiless as the grave, blind as a stone, and as irrational as a headless hen."
~ Ambrose Bierce (born: 1842-06-24 died: 1914 at age: 71)

 

[Roedy Green]

You assume that bit 7 is the parity bit, which it might not be. It
could be that bit 0 is the parity bit. Which bit is the parity bit?

If you are just checking the parity, it does not matter. If you are
trying to strip off the parity it to extract the data, then it does.
--
Roedy Green Canadian Mind Products
http://mindprod.com

"Patriotism is fierce as a fever, pitiless as the grave, blind as a stone, and as irrational as a headless hen."
~ Ambrose Bierce (born: 1842-06-24 died: 1914 at age: 71)

 

[Arne Vajhøj]

Isn't the spelling "nybble"?

Not always.

Arne

 

[Arne Vajhøj]

Not always.

I forgot the link:
http://en.wikipedia.org/wiki/Nibble

Arne

 

[Arne Vajhøj]

the Intel machines compute the parity of the result of almost every
instruction as a side effect and poke it into the condition register.
This means they do it is less than a machine cycle.

I wonder what sort of hardware algorithm they use, perhaps a tree of
xor gates that work in parallel.

A recent Intel CPU contains 731 million transistors - they can
spare a few for this purpose.

Arne

 

[Eric Sosman]

Isn't the spelling "nybble"?

Ny; yt lyks wyrd.

 

[Eric Sosman]

[...]
* Version History:
* 1.0 2009-07-29 - initial version
* 1.1 2009-08-03 - add Eric Sosman's xor method
[...]

Thanks, but I disclaim the "mine." It's one of those
standard bit-fiddling hacks that's been around so long I no
longer recall where I first ran across it. I am certainly
not its inventor.

 

[Eric Sosman]

the Intel machines compute the parity of the result of almost every
instruction as a side effect and poke it into the condition register.
This means they do it is less than a machine cycle.

That goes way back to the 8080, probably even waybacker.

I wonder what sort of hardware algorithm they use, perhaps a tree of
xor gates that work in parallel.

Dunno. That seems straightforward, but I'm no chip designer.

 

[Tom Anderson]

[...]
* Version History:
* 1.0 2009-07-29 - initial version
* 1.1 2009-08-03 - add Eric Sosman's xor method
[...]

Thanks, but I disclaim the "mine." It's one of those standard
bit-fiddling hacks that's been around so long I no longer recall where I
first ran across it. I am certainly not its inventor.

It's one of the hacks in the mighty Bit Twiddling Hacks collection:

http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel

But then, what isn't?

A more definite bit of historical evidence would be to find it in HAKMEM,
but the only parity tricks i can find in that are these:

http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item167
http://www.cl.cam.ac.uk/~am21/hakmemc.html

Which are cuter, but involve multiplies and mods, which these days are
somewhat suspect. It's possible that the HAKMEM authors considered the
'Sosman Trick' too well-known to record, though!

tom

 

[Daniel Pitts]

[...]
* Version History:
* 1.0 2009-07-29 - initial version
* 1.1 2009-08-03 - add Eric Sosman's xor method
[...]

Thanks, but I disclaim the "mine." It's one of those
standard bit-fiddling hacks that's been around so long I no
longer recall where I first ran across it. I am certainly
not its inventor.

I first saw the technique used for a o(logn) bit-count algorithm in a C
header somewhere. I did extrapolate the "parity" approach, but it was
so straight forward that I don't take credit for its invention either