Dev102 Programming Challenge 2

Programming Challenge #2 at Dev102.com is to find an efficient way to reverse the bits in a 1000x1000 byte image. Assuming you can afford 256 bytes for a cache, one really fast general-purpose way to implement this is to create an array with an entry for each possible value of a byte, storing the reversed bits of the byte. For each byte in the image, you can then look the reversed bits nearly instantly. The runtime of the algorithm is O(n) with a trivial constant multiplier.

This algorithm, by the way, is insanely easy to make run in multiple threads and should run extremely fast on a multi-core SIMD processor.