Programming gems (Re: Bit-reversed counting)

[der Mouse]

In article <2818 at ficc.uu.net>, peter at ficc.uu.net (Peter da Silva) writes:
> In article <3891 at ece-csc.UUCP>, jnh at ece-csc.UUCP (Joseph Nathan Hall) writes:
>> In a similar vein, what interesting bit-reversal algorithms are
>> there (distinct from the problem of COUNTING bit-reversed)?
> How about a good algorithm for reversing bits? (the quickest I can
> think off offhand involves table lookup).

This becomes an interesting problem when lots of bits are involved, as
in a bitmap screen.  There's an easy divide-and-conquer algorithm for
reversing a bitmap screen when the width (or height, if you want to
flip it vertically) is a power of two, requiring a second copy for use
as a mask.  (With sufficiently intelligent rasterop (aka bitblt)
algorithms, the extra space needed is only one row, because all rows of
the mask are always identical.)  Here's the essence of the algorithm,
applied to reversing an unsigned int (assumed to be 32 bits):

unsigned int reverseit(unsigned int value)
{
 unsigned int mask;
 int i;

 i = 32;
 mask = ~0;
 while (i > 1)
  { mask ^= mask << i;
    value ^= (value & mask) >> i;
    value ^= (value << i) & mask;
    value ^= (value & mask) >> i;
    i = i / 2;
  }
 return(value);
}

Of course, it's silly to use this for an int, but for a bitmap, it
makes a good deal more sense.  It becomes a more interesting problem
when the size is not a power of two.  I played with the algorithm and
came up with a variant that works for non-powers-of-two.  Since I've
never seen such a variant even referred to anywhere, here it is....
Again, it's applied to reversing an int, but this time the number of
bits is passed in as a parameter.  It should be clear how to extend
this to the case when value and mask are really bitmap arrays (and
width_in_bits is somewhat larger).  I have a program that flips a Sun
screen using this algorithm, so it definitely works.

unsigned int reverse(unsigned int value, int width_in_bits)
{
 unsigned int mask;
 int w;
 int w2;
 int lastodd;

 w = width_in_bits;
 mask = (1UL << w) - 1UL;
 /* the above assumes w is less than the number of bits in mask,
    or that << returns 0 when w equals that number. */
 lastodd = 0;
 while (w > 1)
  { w2 = w - (w / 2);
    mask &= mask << w2;
    mask |= mask >> (w+lastodd);
    value ^= mask & (value << w2);
    value ^= (mask & value) >> w2;
    value ^= mask & (value << w2);
    lastodd = w & 1;
    w -= w2;
  }
 return(value);
}

Is this new?  Surely not....but it isn't too widely known (translation:
I never heard of it anywhere :-).

					der Mouse

			old: mcgill-vision!mouse
			new: mouse at larry.mcrcim.mcgill.edu