Macro - Generating look up table for 4 bits

Question

Below is the look up table for bit reversal(8 bits)

  static const unsigned char BitReverseTable256[256] = 
{
  #   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
  #   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
  #   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
      R6(0), R6(2), R6(1), R6(3)
};

Below link explain the algo behind it.But I didn't understood it completely. Look-up table for 8 bit reversal

I want the similar kind of macro for 4 bit reversal, so that I can understand the 8 bit. Can somebody provide the same macro for 4 bit reversal.

Thanks,

You can provide it by adapting the 8-bit version. Take a try at it. — nicomp, Jul 14 '18 at 19:38
The best way to create it is to work out for yourself how to do it. Think about what you're going to need. How big is the array going to be? What should the values in each cell be? The code shown generates 4 values per invocation of `R2`; how many should your analogue of `R2` create? Are you sure a macro-based solution is a good idea for reversing 4-bit values? — Jonathan Leffler, Jul 14 '18 at 19:38

score 1 · Answer 1 · answered Apr 26 '20 at 17:33

For 4-bit integers, your lookup table will be of size 16, that is, pow(2, 4). I will begin by enumerating manually so that we can find out whether there is a pattern:

Integer  Binary Representation  Reverse Binary Representation   Reverse Value

0            0000                        0000                        0
1            0001                        1000                        8
2            0010                        0100                        4
3            0011                        1100                        12
4            0100                        0010                        2
5            0101                        1010                        10
6            0110                        0110                        6
7            0111                        1110                        14
8            1000                        0001                        1
9            1001                        1001                        9 
10           1010                        0101                        5
11           1011                        1101                        13
12           1100                        0011                        3
13           1101                        1011                        11
14           1110                        0111                        7
15           1111                        1111                        15

Notice that in the Reverse Binary Representation column, the leftmost(most significant 2 bits) increase the same way, i.e, 00 10 01 11 every fourth time.

Similarly, notice that in the Reverse Binary Representation column, the rightmost(least significant 2 bits) also adopt the same pattern i.e, 00 10 01 11 but four times at a go.

The numbers, 0 1 2 3, in binary are, 00 01 10 11, and if you reverse each: 00 10 01 11, you get, 0 2 1 3!

0 2 1 3 shall be the building block and we shall generalize using the following equation:

n, n + 2 * 4, n + 1 * 4, n + 3 * 4

Hint: Try to derive the column Reverse Value using the equation above. Example, First four values are derived from n = 0

0         = 0
0 + 2 * 4 = 8
0 + 1 * 4 = 4
0 + 3 * 4 = 12

I haven't written C in a long time but I suppose you shall have(I stand to be corrected):

static const unsigned char BitReverseTable[16] = 
{
     define R2(n) n, n + 2*4, n + 1*4, n + 3*4
     R2(0), R2(2), R2(1), R2(3)
};

In Python:

def R2(n, FOUR_BIT_LUT):
    FOUR_BIT_LUT.extend([n, n + 2 * 4, n + 1 * 4, n + 3 * 4])


def LOOK_UP(FOUR_BIT_LUT):
    return (
        R2(0, FOUR_BIT_LUT),
        R2(2, FOUR_BIT_LUT),
        R2(1, FOUR_BIT_LUT),
        R2(3, FOUR_BIT_LUT),
    )


FOUR_BIT_LUT = list()
LOOK_UP(FOUR_BIT_LUT)

print(FOUR_BIT_LUT) # [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

However, a macro-based solution might be overkill for 4-bits. You could just initialise an array of reverse values.

Anyway, I do hope that this helps you understand the pattern.

Macro - Generating look up table for 4 bits

1 Answers1