|
|
Reverse an N-bit quantity in parallel in 7 * lg(N) operations:unsigned int v; // 32 bit word to reverse bit order
const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};v = ((v >> S[0]) & B[0]) | ((v << S[0]) & ~B[0]); // swap odd and even bits
v = ((v >> S[1]) & B[1]) | ((v << S[1]) & ~B[1]); // swap consecutive pairs
v = ((v >> S[2]) & B[2]) | ((v << S[2]) & ~B[2]); // swap nibbles ...
v = ((v >> S[3]) & B[3]) | ((v << S[3]) & ~B[3]);
v = ((v >> S[4]) & B[4]) | ((v << S[4]) & ~B[4]);This method is best suited to situations where N is large.
Any reasonable optimizing C compiler should treat the dereferences of B, ~B, and S as constants, requiring no evaluation other than perhaps a load operation for some of the B and ~B references.
See Dr. Dobb's Journal 1983, Edwin Freed's article on Binary Magic Numbers for more information.
E-mail: 
info@telesys.ru
