Re: bit operations and parity
Roedy Green wrote:
[...] Eric Sosman's xor method
Eric Sosman wrote:
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.
--
Lew