时间戳

首页 > 解决方案 > 在 C 中使用按位运算的 2 位映射

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

问题描述

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

我有一个问题，我必须映射一个可以在 (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; 
}

标签： cmappingbit-manipulationbitwise-operators

解决方案

经过思考，并使用其他答案的一些想法，我想我找到了一个通用的解决方案。它基于首先估计值，假设只有键 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; 
}

推荐阅读