On: Rediscovering Hamming Code

[anonymousiam]

Re: "fast" parity code in article. I always preferred the parity example from the (pre-ansi) K&R C Programming Language book:

#include <stdio.h>

main( argc, argv ) int argc; char *argv[];

{

    unsigned source;

    int parity;

    if ( argc > 1 )
    {
        if ( sscanf( argv[1], "%d", &source ) == 1 )
        {
            printf( "%d = ", source );
            for ( parity = 0; source; parity++ )
                source &= ( source - 1 );
            printf( "%d\n", parity & 1 );
        }
    }

}

The function in the article is faster for > 8-bit values when there are more than eight ones in the value being checked. Also, I suppose theirs is better than K&R because it always executes in the same number of cycles.

[juxhindb → anonymousiam]

Thanks for sharing that, love the simplicity behind it which is more intuitive than the example I had gone with.

I think the reason why I chose that particular one was to show how thinking about a problem from an entirely different angle can yield great (and rewarding) results.

[saagarjha → juxhindb]

Ideally, you'd want your compiler to use the hardware population count instructions though. So this might be one of the places where a simpler algorithm might win out because the compiler can recognize it.

[juxhindb → saagarjha]

In fact that is one of the follow-ups I want to have out of this. Have architecture-specific optimisations (popcnt on x86) either manually through something like the `asm` crate, or by having a simpler algorithm that the compiler can optimise away.

[juxhindb → juxhindb]

An extension to this infact is the following - https://github.com/llvm-mirror/llvm/blob/f36485f7ac2a8d72ad0...

So the original user's comment might infact get detected by this and get optimised down to using popcnt. Will need to try it out. :-)