c - 在 C 中使用按位运算的 2 位映射

Question

这是我的第一个问题，所以我希望做对。

我有一个问题，我必须映射一个可以在 (0, 1, 2) 范围内的键才能从相同的范围 (0, 1, 2) 中选择一个值。我必须重复数百万次，我试图通过在 C 中使用按位运算来实现这一点，但没有成功。

因此，假设我在 (0, 1, 2) 范围内有 16 个键，我想使用以下规则将它们映射到同一范围内的 16 个值:

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

我可以将 16 个键的数组表示为 32 位无符号整数中的 16 个 2 位对。例如:

  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

我对转换无符号整数感兴趣，遵循上述规则(即必须按照规则转换 2 位对:00->10、01->01 和 10->01)，这样我就结束了使用 32 位无符号整数，如:

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

它是一个相对较快的按位过程，可以让我有效地应用这种转换(假设转换规则可以改变)？

我希望我清楚地表达了我的问题。谢谢你的帮助。

编辑:我纠正了一些错误，并在评论后澄清了一些观点。

EDIT2:根据一些建议，我添加了我希望的代码示例:

#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

这本质上是将真值表简化为最小 bool 表达式的问题；这里我们需要两个表达式，每个输出值位一个。

BA QP

00 10
01 01
10 01
11 XX

B:高值位，A:低值位，Q:高值位，P:低值位

通过使用任何可用的工具(包括我们的大脑)来最小化 combinational logic 电路，我们得到表达式

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

现在我们有了表达式，我们可以将它们应用于 32 位变量中的所有键:

    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.

这是一个用于任意映射的示例程序。对于两个值位中的每一个，都有 23 种可能的表达式(两个位的集合相同)；这些表达是:

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

通过分别连接键 0、1 和 2 的高映射位和低映射位，我们得到与映射函数对应的表达式的索引。在下面的程序中，所有表达式的值，甚至是映射未使用的值，都存储在 term 数组中。虽然这看起来很浪费，但它允许没有分支的计算，这最终可能是一个胜利。

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