bit operations and parity

[Lew]

[...] 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.

Just for fun, I looked up the source for Java 6's Integer.bitCount(int i).

It's substantially similar to
<http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel>
(thanks, tom!)
but doesn't use B[3] and B[4], rather, the Java code skips those two & ops
then &s the penultimate "c" value ('i' in the Java source) with 0x3f.

My earlier suggestion (paraphrased):

int parity = Integer.bitCount( theByte & 0xff ) & 0x01;

has 2 more shift ops, 6 more & ops, 5 adds/subtracts vs. 3 XORs and 2 more
assignments than the byte-specific algorithm Eric cited:

int parity = theByte ^ (theByte >> 4);
parity ^= parity >> 2;
parity ^= parity >> 1;
parity &= 1;

or 20 vs. 8 operations overall.

Whether that difference matters to application performance depends on how much
it's called and in what contexts. Checking bytes streaming in from an I/O
device, the difference probably won't matter. Then it's a question of which
source is more readable, self-documenting and maintainable.

 

[Roedy Green]

Then it's a question of which
source is more readable, self-documenting and maintainable.

maintainable? That is usually a consideration, but here?
--
Roedy Green Canadian Mind Products
http://mindprod.com

"Change will not come if we wait for some other person or some other time. We are the ones we’ve been waiting for. We are the change that we seek."
~ Barack Obama (born: 1961-08-04 age: 48)