2-bit mapping using bitwise operations in C

Question

This is my first question, so I hope to do this right.

I have a problem where I have to map a key which can be in the range (0, 1, 2) to select a value from the same range (0, 1, 2). I have to repeat this millions of times and I was trying to implement this by using bitwise operations in C, without success.

So let's say I have 16 keys in the range (0, 1, 2) which I want to map to 16 values in the same range by using the following rules:

0 -> 2
1 -> 1
2 -> 1

I can represent the array of 16 keys as 16 2-bit pairs in a 32bit unsigned int. For instance:

  0, 1, 2, 1, 2, 0, ... //Original array of keys
 00 01 10 01 10 00 ...  //2-bit pairs representation of keys in a 32bit int

and I am interested in transforming the unsigned int, following the rules above (i.e. the 2-bit pairs have to be transformed following the rules: 00->10, 01->01, and 10->01), so that I end up with a 32bit unsigned int like:

 10 01 01 01 01 10 ...  //2-bit pairs transformed using the given rule.

Would it be a relatively fast bitwise procedure which will allow me to apply efficiently this transformation (given that the transformation rules can change)?

I hope I formulated my question clearly. Thanks for any help.

EDIT: I corrected some mistakes, and clarified some points following comments.

EDIT2: Following some suggestions, I add what I hope is a code example:

#include <stdio.h> 
#include <stdlib.h> 

int main(void) 
{ 
    int i;

    unsigned int keys[16];
    unsigned int bitKeys = 0;

    unsigned int mapping[3];

    unsigned int result[16];
    unsigned int bitResults = 0;

    //Initialize random keys and mapping dict    
    for(i = 0; i<16; i++) 
        keys[i] = rand() % 3;
        bitKeys |= keys[i] << (2*i);

    for(i = 0; i<3; i++) 
        mapping[i] = rand() % 3; 

    //Get results without using bitwise opperations.
    for(i = 0; i<16; i++) 
        result[i] = mapping[ keys[i] ];
        bitResults |= result[i] << (2*i);


    //Would it be possible to get bitResults directly from bitKeys efficiently by using bitwise operations?


    return 0; 
} 

Answer 1

This is essentially a problem of simplifying truth tables to minimal Boolean expressions; here we need two expressions, one for each output value bit.

BA QP

00 10
01 01
10 01
11 XX

B: high key bit, A: low key bit, Q: high value bit, P: low value bit

By using any of the many tools available (including our brain) for minimizing combinational logic circuits, we get the expressions

Q = ¬A·¬B
P = A + B

Now that we have the expressions, we can apply them to all keys in a 32-bit variable:

    uint32_t keys = 2<<30|0<<10|1<<8|2<<6|1<<4|2<<2|0;  // for example
    uint32_t vals = ~keys & ~keys<<1 & 0xAAAAAAAA   // value_high is !key_high & !key_low
                  | (keys>>1 | keys) & 0x55555555;  // value_low is key_high | key_low

I would need a solution for any arbitrary mapping.

Here's an example program for arbitrary mappings. For each of the two value bits, there are 2³ possible expressions (the same set for both bits); these expressions are:

0    ¬A·¬B    A    ¬B    B    ¬A    A+B    1

By concatenating the high and low mapping bits, respectively, for keys 0, 1 and 2, we get the index of the expression corresponding to the mapping function. In the following program, the values of all the expressions, even the ones unused by the mapping, are stored in the term array. While this may seem wasteful, it allows computation without branches, which may be a win in the end.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main()
{
    int i;
    unsigned mapping[3];
    // generate example mapping
    for (i = 0; i < 3; ++i) mapping[i] = rand() % 3, printf(" %d->%d", i, mapping[i]);
    puts("");

    // determine the mapping expression index 0..7 for high and low value bit
    short h = mapping[0]/2 | mapping[1]/2<<1 | mapping[2]/2<<2;
    short l = mapping[0]%2 | mapping[1]%2<<1 | mapping[2]%2<<2;

    uint32_t keys = 0x1245689A; // for example

    uint32_t b = keys, a = keys<<1;
    uint32_t term[8] = { 0, ~a&~b, a, ~b, b, ~a, a|b, -1 };  // all possible terms
    uint32_t vals = term[h]    & 0xAAAAAAAA   // value_high
                  | term[l]>>1 & 0x55555555;  // value_low
    printf("%8x\n%8x\n", keys, vals);
}