# Bit Reverse
### 1. Problem Definition
Given an intger $B$ of $\lambda$ bits represented $b_{\lambda-1}...b_1b_0$, the bit reversal of $B$ is $b_0b_1...b_{\lambda-1}$; that is, $bitReversal(B) = b_0b_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_2b_1b_0$| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| $b_0b_1b_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.
``` C=
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^i_{\lambda-1}...b^i_1b^i_0$. We simply denote $b^i_j$ 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{align}\qquad br[i][j] = data[i][\lambda-j-1] \qquad \qquad \qquad[1]
\end{align} for $0\le j \le \lambda-1$.
**Algorithm 1**
```C=
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.
``` C=
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]
```
``` C=
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]
```
``` C=
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)
```
``` c=
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;
}
}
}
```
Sign in with Wallet
Connect another wallet