peter@ficc.uu.net (Peter da Silva) (01/20/89)
In article <3891@ece-csc.UUCP>, jnh@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). -- Peter da Silva, Xenix Support, Ferranti International Controls Corporation. Work: uunet.uu.net!ficc!peter, peter@ficc.uu.net, +1 713 274 5180. `-_-' Home: bigtex!texbell!sugar!peter, peter@sugar.uu.net. 'U` Opinions may not represent the policies of FICC or the Xenix Support group.
hoey@ai.etl.army.mil (Dan Hoey) (01/25/89)
Several bit permutations can be achieved by shifting a subset of the bits of an
N-bit number O(N) times. Most of the interesting ones are characterized by
moving bit I to bit R(I) where R is a function that permutes the bits of its
argument and complements some subset of those bits. Common examples of such
permutations are reversing the bits, performing a perfect shuffle on the bits,
and--approximately--a couple of the permutations used in the DES encryption
standard. For reversing the bits of a 32-bit number, the following code
suffices.
long BitRev(n) register long n;{
n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
return n;
}mouse@mcgill-vision.UUCP (der Mouse) (02/01/89)
In article <2818@ficc.uu.net>, peter@ficc.uu.net (Peter da Silva) writes: > In article <3891@ece-csc.UUCP>, jnh@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@larry.mcrcim.mcgill.edu