Path: utzoo!attcan!uunet!lll-winken!ames!ai.etl.army.mil!hoey
From: hoey@ai.etl.army.mil (Dan Hoey)
Newsgroups: comp.lang.c
Subject: Re: Programming gems (Bit-reversed counting)
Message-ID: <246@ai.etl.army.mil>
Date: 24 Jan 89 20:21:35 GMT
References: <3891@ece-csc.UUCP> <2818@ficc.uu.net>
Reply-To: hoey@ai.etl.army.mil (Dan Hoey)
Organization: Naval Research Lab, Washington, DC
Lines: 19

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;
}