Bit Reverse

1. Problem Definition

Given an intger

$B$ of

$\lambda$ bits represented

$b_{\lambda -1}...b_1{b}_0$, the bit reversal of

$B$ is

$b_0{b}_1...b_{\lambda -1}$; that is,

$bitReversal(B)=b_0{b}_1...b_{\lambda -1}$.

In this note, we would like to design algorithms to bit-reverse all

$2^{\lambda }$ integers of

$\lambda$ bits. Below shows an example for the case of

$n$ = 8 (=

$2^3$):

$B$	0	1	2	3	4	5	6	7
$b_2{b}_1{b}_0$	000	001	010	011	100	101	110	111
$b_0{b}_1{b}_2$	000	100	010	110	001	101	011	111
$bitReversal(B)$	0	4	2	6	1	5	3	7

2. Sequential Algorithms

Let

$0,1,2,...,n$ be stored in

$data[0],data[1],data[n-1]$ and their bit-reversal forms be stored in

$br[0],br[1],br[n-1]$, respectively.

unsigned int data[SIZE]
input: 0, 1, 2, ⋯, n-1 stored in data[0], data[1], ⋯, data[n-1]
output: br[0], br[1], ⋯, br[n-1] when br[i] is the bit reverse of data[i]

Consider

$data[i]=b_{\lambda -1}^i...b_1^i{b}_0^i$. We simply denote

$b_j^i$ as

$data[i][j]$ where

$0\le i\le n-1$ and

$0\le j\le \lambda -1$.

A naive algorithm assigns

$br[i][j]$ as

$data[i][\lambda -j-1]$. For the case of

$\lambda =3$,

$br[i][0]=data[i][2],br[i][1]=data[i][1]$ and

$br[i][2]=data[i][0]$. In short,

$$\begin{array}{r}br[i][j]=data[i][\lambda -j-1][1]\end{array}$$ for

$0\le j\le \lambda -1$.

Algorithm 1

read(n);
bit_len = log2(n) // n = 2＾k, bit_len = k 
for (i = 0; i < n; i++)
    for (j = 0; j < bit_len; j++)
        br[i][j] = data[i][bit_len-j-1];

There are quite a few implementations of Eq.

$[1]$. Below show some of them.

for (j=0; j<bit_len; j++)
    mask[j] = 1 << j;   
for (i = 0; i < n; i++)
{   br[i] = 0;
    x = data[i];
    for (j = 0; j < bit_len; j++)
    {   br[i] |= x & mask[bit_len-j-1];
                 // filtering the jth bit of data[i]
    }
}
// let mask[j] = 2^j
// br[i] |= data[i] & mask[bit_len-j-1]

for (j=0; j<bit_len; j++)
    rMask[j] = 1 << (bit_len-j-1);   
for (i = 0; i < n; i++)
{   br[i] = 0;    
    x = data[i];
    for (j = 0; j < bit_len; j++)
    {   br[i] |= x & rMask[j];
                 // filtering the (bit_len-j-1)th bit of data[i]
    }
}
// let rMask[j] = 2^(bit_len-j-1)
// br[i] |= data[i] & rMask[j]

for (i = 0; i < n; i++)
{   br[i] = 0;    
    x = data[i];
    y = bit_len-1;
    for (r = 0; r<bit_len ; r++)
    {   br[i] |= (x>>y) << r;                
        x <<= 1;        
    } // br[i][r] = data[i][bit_len-1-r]
}
// data [i][bit_len-i-1]
// br[i] |= (data[i]>>(r-1))<<(bit_len-r-1)
// for (r = bit_len-i-1; r>0 ; r--)
//    br[i] |= (data[i]>>(r-1))<<(bit_len-1-r)

void bitReversal_A1(unsigned long long * data, unsigned long long n, int logN, unsigned long long * br)
{   // unsigned long long mask = ((unsigned long long) 1 << logN) - 1 ;
    unsigned long long mask = n - 1 ;
    unsigned long long result, x;
    int shiftR = logN-1, r, k;
    // cout << "A1==> n=" << n << ", logN=" << logN << ", mask=" << mask << ", shiftR=" << shiftR << endl;
    for (k=0; k<n; k++)
    {   x = data[k];
        for (result=0, r=0; r<logN ; r++)
        {   result |= (x>>shiftR) << r;
            x = (x << 1) & mask;
            // cout << ", result=" << result << ", x=" << x ;
        } // br[i][r] = data[i][logN-1-r]
        // cout << endl;
        br[k] = result;
    }
}

void bitReversal_A1_1(unsigned long long * data, unsigned long long n, int logN, unsigned long long * br)
{   unsigned long long rev, x, mask = n-1;
    int i, j;
    for (i=0; i<n; i++)
    {   rev = 0;
        for (rev=0, x=data[i], mask=n-1; mask; x>>=1, mask>>=1)
        {   rev <<= 1;
            if (x & 1 == 1) rev ^= 1;
        }
        /*
        mask = n-1 ;
        while (mask)
        {   rev <<= 1;
            if (x & 1 == 1) rev ^= 1;
            // cout << "mask=" << mask << ", logN=" << logN << ", rev=" << rev << ", x=" << x << endl;
            x >>= 1;
            mask >>= 1;

        }
        */
        br[i] = rev;
    }
}

void bitReversal_A2(unsigned long long data [], unsigned long long n, int logN, unsigned long long br [])
{   // unsigned long long mask = ((unsigned long long)1 << logN) - 1, x ;
    unsigned long long mask, x ;
    // unsigned int offset = (bitLen & 1) ? (bitLen >> 1)+1 : bitLen >> 1 ;
    int offset  ;
    int i, k;
    int tmp, ext, extLogN, logLogN;
    for (tmp=logN, extLogN=2; (tmp>>=1); extLogN<<=1);
    if ((logN<<1) == extLogN) extLogN = logN;
    logLogN = log2(extLogN);
    ext = extLogN - logN;
    // cout << "logN=" << logN << ", extLogN=" << extLogN << ", ext=" << ext << ", logLogN=" << logLogN << ", offset=" << offset << endl;
    for (k=0; k<n; k++)
    {   x = data [k];
        for (mask=((unsigned long long)1 << extLogN)-1, offset=extLogN>>1, i=0; i<logLogN; i++)
        {   mask ^= mask >> offset;
            x = ((x & mask) >> offset) | ((x & ~mask) << offset);
            offset >>= 1;
            // cout << "mask=" << mask << ", offset=" << offset << ", x=" << x << endl;
        }
        br[k] = (ext) ? x>>=ext : x ;
        // br[k] = x;
        // if (ext) br[k]>>=ext;
    }
}

void bitReversal_A3(unsigned long long data [], unsigned long long n, unsigned long long br [])
{   unsigned long long tmp, m;
    int i, j;
    for (i=0; i<n; i++)
        br[i] = data[i];
	for (i=0, j=0; i<n; i++)
	{   if (j > i)
            SWAP(br[i], br[j], tmp);
		for (m = n>>1; m>=2 && j >= m; j-=m, m>>=1);
        j += m;
	}
}
void bitReversal_A3_1(unsigned long long data [], unsigned long long n, unsigned long long br [])
{   unsigned long long tmp, m;
    int i, j=0;
    for (i=0; i<n; i++)
        br[i] = data[i];
	for (i=1, j|=(n>>1); i<n-1; i++)
	{   if (j > i)
        {   br[i] = j;
            br[j] = i;
        }    //SWAP(br[i], br[j], tmp);
		// for (m = n>>1; m>=2 && j >= m; j-=m, m>>=1);
        // j += m;
        // m = n;
        // while (j & (m >>= 1)) j &= ~m;
        for (m = n; j & (m >>= 1); j &= ~m) ;
        j |= m;
	}
}
void bitReversal_A3_2(unsigned long long data [], unsigned long long n, unsigned long long br [])
{   unsigned long long tmp, m;
    int i, j=0;
    // for (i=0; i<n; i++)
    //    br[i] = i;
	for (i=1, j|=(n>>1); i<n-1; i++)
	{   if (j > i)
        {   br[i] = j;
            br[j] = i;
        }    // SWAP(br[i], br[j], tmp);
        else br[i] = j;
        // else br[i] = j;
		// for (m = n>>1; m>=2 && j >= m; j-=m, m>>=1);
        // j += m;
        // m = n;
        // while (j & (m >>= 1)) j &= ~m;
        for (m = n; j & (m >>= 1); j &= ~m) ;
        j |= m;
        // br[i] = j;
	}
}
// n = 2^k 
// unsigned int Mask = n;
// Search for the first 0 from MSB to LSB and replace all 0s as 1s (including the first 0). 
// while (j & (Mask >>= 1))
//       j &= ~Mask;
//  碰到第一個 0 所在的那個位置改成 1
// j |= Mask;
// Gold Rader bit reversal algorithm

void bitReversal_A4(unsigned long long data [], unsigned long long n, unsigned long long br [])
{   unsigned long long step;
    int i, j;
    for (i=0; i<n; i++) br[i] = 0;
    for (step=1; step<n; step<<=1)
    {   for (j=0; j<step; j++)
        {   // br[j]<<= 1;
            br[j+step] = (br[j]<<=1) + 1;
            // cout << "step=" << step << ", br[" << j << "]=" << br[j] << ", br[" << j+step << "]=" << br[j+step] << endl;
        }
    }
}