在 C 中使用按位运算的 2 位映射
2-bit mapping using bitwise operations in C
这是我的第一个问题，所以我希望做对。
我有一个问题，我必须将一个可以在 (0, 1, 2) 范围内的键映射到 select 来自相同范围 (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
我有兴趣按照上述规则转换 unsigned 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;
}
这本质上是一个将真值表简化为最小布尔表达式的问题；这里我们需要两个表达式，一个用于每个输出值位。
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);
}
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
这当然可以做到，但是对于从 { 0, 1, 2 } 到 { 0, 1, 2 } 的 27 个不同映射中的每一个，所需的操作顺序都是不同的。有些可以非常简单，例如三个常量映射，但有些则需要更复杂的表达式。
在没有进行彻底分析的情况下，我倾向于猜测既不是常量也不是排列的映射，例如示例中显示的映射，可能具有最大的最小复杂度。这些都有一个特征，即两个键映射到相同的值，而另一个键映射到不同的值。一种方法——不一定是最好的——为这种映射寻找表达式的方法是首先关注实现两个键映射到一个值而另一个映射到不同值的一般结果，然后继续转换如有必要，将结果值设置为所需值。
举个例子，
0 -> 2
1 -> 1
2 -> 1
，可以（在每个键的基础上）使用 ((key & 2) >> 1) | ((key & 1) << 1) 来获得这些初步结果：
0 -> 0
1 -> 3
2 -> 3
，可以通过异或运算翻转高位，将其转换为所需的最终结果。
注意位掩码。还有其他方法可以用来映射单个键，但是对于多个键存储在同一整数的连续位中的情况，您需要小心避免用来自不同键的数据污染计算的映射。
在 16 项位向量形式中，这将是
uint32_t keys = /*...*/;
uint32_t values = (((keys & 0xAAAAAAAAu) >> 1) | ((keys & 0x55555555u) << 1))
^ 0xAAAAAAAAu;
。到目前为止，这恰好比您其他答案中的表达式少了几个操作，但我不确定它是否是可能的最小操作数。事实上，如果你准备接受 arithmetic 除了按位运算，那么你绝对可以用更少的运算来做到：
uint32_t keys = /*...*/;
uint32_t values = 0xAAAAAAAAu
- (((keys & 0xAAAAAAAAu) >> 1) | (keys & 0x55555555u));
当然，在一般情况下，各种操作的成本并不都相同，但整数加减法和按位与、或、异或在大多数架构上都具有相同的成本（例如，参见 https://www.agner.org/optimize/instruction_tables.pdf).
经过深思熟虑，并参考了其他答案的一些想法，我想我找到了一个通用的解决方案。它基于首先估计值，假设只有键 10 和 01（即一对中的一位决定另一位），然后通过键 00 进行校正。解决方案的示例代码：
#include <stdio.h>
#include <stdlib.h>
void printBits(size_t const size, void const * const ptr)
{
unsigned char *b = (unsigned char*) ptr;
unsigned char byte;
int i, j;
for (i=size-1;i>=0;i--)
{
for (j=7;j>=0;j--)
{
byte = (b[i] >> j) & 1;
printf("%u", byte);
if(j%2 == 0) printf("|");
}
}
puts("");
}
int test2BitMapping(unsigned int * mapping)
{
int i;
unsigned int keys[16];
unsigned int bitKeys = 0;
unsigned int b = 0;
unsigned int c = 0;
unsigned int d = 0;
unsigned int expand[4] = {0x00000000u, 0x55555555u, 0xAAAAAAAAu, 0xFFFFFFFFu};
unsigned int v12 = 0;
unsigned int v0mask = 0;
unsigned int result[16];
unsigned int bitResults = 0;
unsigned int bitResultsTest = 0;
//Create mapping masks
b = ((1 & mapping[1]) | (2 & mapping[2]));
c = (2 & mapping[1]) | (1 & mapping[2]);
d = mapping[0];
b = expand[b];
c = expand[c];
d = expand[d];
//Initialize random keys
for(i = 0; i<16; i++) {
if(0) { //Test random keys
keys[i] = rand() % 3;
}
else { //Check all keys are generated
keys[i] = i % 3;
}
bitKeys |= keys[i] << (2*i);
}
//Get results without using bitwise opperations.
for(i = 0; i<16; i++) {
result[i] = mapping[ keys[i] ];
bitResultsTest |= result[i] << (2*i);
}
//Get results by using bitwise opperations.
v12 = ( bitKeys & b ) | ( (~bitKeys) & c );
v0mask = bitKeys | (((bitKeys & 0xAAAAAAAAu) >> 1) | ((bitKeys & 0x55555555u) << 1));
bitResults = ( d & (~v0mask) ) | ( v12 & v0mask );
//Check results
if(0) {
for(i = 0; i<3; i++) {
printf("%d -> %d, ", i, mapping[i]);
}
printf("\n");
printBits(sizeof(unsigned int), &bitKeys);
printBits(sizeof(unsigned int), &bitResults);
printBits(sizeof(unsigned int), &bitResultsTest);
printf("-------\n");
}
if(bitResults != bitResultsTest) {
printf("*********\nDifferent\n*********\n");
}
else {
printf("OK\n");
}
}
int main(void)
{
int i, j, k;
unsigned int mapping[3];
//Test using random mapping
for(k = 0; k < 1000; k++) {
for(i = 0; i<3; i++) {
mapping[i] = rand() % 3;
}
test2BitMapping(mapping);
}
//Test all possible mappings
for(i = 0; i<3; i++) {
for(j = 0; j<3; j++) {
for(k = 0; k<3; k++) {
mapping[0] = i;
mapping[1] = j;
mapping[2] = k;
test2BitMapping(mapping);
}
}
}
return 0;
}
这是我的第一个问题，所以我希望做对。
我有一个问题，我必须将一个可以在 (0, 1, 2) 范围内的键映射到 select 来自相同范围 (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
我有兴趣按照上述规则转换 unsigned 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;
}
这本质上是一个将真值表简化为最小布尔表达式的问题；这里我们需要两个表达式，一个用于每个输出值位。
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);
}
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
这当然可以做到，但是对于从 { 0, 1, 2 } 到 { 0, 1, 2 } 的 27 个不同映射中的每一个，所需的操作顺序都是不同的。有些可以非常简单，例如三个常量映射，但有些则需要更复杂的表达式。
在没有进行彻底分析的情况下，我倾向于猜测既不是常量也不是排列的映射，例如示例中显示的映射，可能具有最大的最小复杂度。这些都有一个特征，即两个键映射到相同的值，而另一个键映射到不同的值。一种方法——不一定是最好的——为这种映射寻找表达式的方法是首先关注实现两个键映射到一个值而另一个映射到不同值的一般结果，然后继续转换如有必要，将结果值设置为所需值。
举个例子，
0 -> 2 1 -> 1 2 -> 1
，可以（在每个键的基础上）使用 ((key & 2) >> 1) | ((key & 1) << 1) 来获得这些初步结果：
0 -> 0
1 -> 3
2 -> 3
，可以通过异或运算翻转高位，将其转换为所需的最终结果。
注意位掩码。还有其他方法可以用来映射单个键，但是对于多个键存储在同一整数的连续位中的情况，您需要小心避免用来自不同键的数据污染计算的映射。
在 16 项位向量形式中，这将是
uint32_t keys = /*...*/;
uint32_t values = (((keys & 0xAAAAAAAAu) >> 1) | ((keys & 0x55555555u) << 1))
^ 0xAAAAAAAAu;
。到目前为止，这恰好比您其他答案中的表达式少了几个操作，但我不确定它是否是可能的最小操作数。事实上，如果你准备接受 arithmetic 除了按位运算，那么你绝对可以用更少的运算来做到：
uint32_t keys = /*...*/;
uint32_t values = 0xAAAAAAAAu
- (((keys & 0xAAAAAAAAu) >> 1) | (keys & 0x55555555u));
当然，在一般情况下，各种操作的成本并不都相同，但整数加减法和按位与、或、异或在大多数架构上都具有相同的成本（例如，参见 https://www.agner.org/optimize/instruction_tables.pdf).
经过深思熟虑，并参考了其他答案的一些想法，我想我找到了一个通用的解决方案。它基于首先估计值，假设只有键 10 和 01（即一对中的一位决定另一位），然后通过键 00 进行校正。解决方案的示例代码：
#include <stdio.h>
#include <stdlib.h>
void printBits(size_t const size, void const * const ptr)
{
unsigned char *b = (unsigned char*) ptr;
unsigned char byte;
int i, j;
for (i=size-1;i>=0;i--)
{
for (j=7;j>=0;j--)
{
byte = (b[i] >> j) & 1;
printf("%u", byte);
if(j%2 == 0) printf("|");
}
}
puts("");
}
int test2BitMapping(unsigned int * mapping)
{
int i;
unsigned int keys[16];
unsigned int bitKeys = 0;
unsigned int b = 0;
unsigned int c = 0;
unsigned int d = 0;
unsigned int expand[4] = {0x00000000u, 0x55555555u, 0xAAAAAAAAu, 0xFFFFFFFFu};
unsigned int v12 = 0;
unsigned int v0mask = 0;
unsigned int result[16];
unsigned int bitResults = 0;
unsigned int bitResultsTest = 0;
//Create mapping masks
b = ((1 & mapping[1]) | (2 & mapping[2]));
c = (2 & mapping[1]) | (1 & mapping[2]);
d = mapping[0];
b = expand[b];
c = expand[c];
d = expand[d];
//Initialize random keys
for(i = 0; i<16; i++) {
if(0) { //Test random keys
keys[i] = rand() % 3;
}
else { //Check all keys are generated
keys[i] = i % 3;
}
bitKeys |= keys[i] << (2*i);
}
//Get results without using bitwise opperations.
for(i = 0; i<16; i++) {
result[i] = mapping[ keys[i] ];
bitResultsTest |= result[i] << (2*i);
}
//Get results by using bitwise opperations.
v12 = ( bitKeys & b ) | ( (~bitKeys) & c );
v0mask = bitKeys | (((bitKeys & 0xAAAAAAAAu) >> 1) | ((bitKeys & 0x55555555u) << 1));
bitResults = ( d & (~v0mask) ) | ( v12 & v0mask );
//Check results
if(0) {
for(i = 0; i<3; i++) {
printf("%d -> %d, ", i, mapping[i]);
}
printf("\n");
printBits(sizeof(unsigned int), &bitKeys);
printBits(sizeof(unsigned int), &bitResults);
printBits(sizeof(unsigned int), &bitResultsTest);
printf("-------\n");
}
if(bitResults != bitResultsTest) {
printf("*********\nDifferent\n*********\n");
}
else {
printf("OK\n");
}
}
int main(void)
{
int i, j, k;
unsigned int mapping[3];
//Test using random mapping
for(k = 0; k < 1000; k++) {
for(i = 0; i<3; i++) {
mapping[i] = rand() % 3;
}
test2BitMapping(mapping);
}
//Test all possible mappings
for(i = 0; i<3; i++) {
for(j = 0; j<3; j++) {
for(k = 0; k<3; k++) {
mapping[0] = i;
mapping[1] = j;
mapping[2] = k;
test2BitMapping(mapping);
}
}
}
return 0;
}