2-битное отображение с использованием побитовых операций в C

Question

Это мой первый вопрос, поэтому я надеюсь сделать это правильно.

У меня проблема с тем, что мне нужно сопоставить ключ, который может находиться в диапазоне (0, 1, 2), чтобы выбрать значение из того же диапазона (0, 1, 2). Я должен повторить это миллионы раз, и я пытался реализовать это с помощью побитовых операций в C, но безуспешно.

Итак, допустим, у меня есть 16 ключей в диапазоне (0, 1, 2) который я хочу отобразить на 16 значений в том же диапазоне, используя следующие правила:

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

Я могу представить массив из 16 ключей в виде 16 2-битных пар в 32-битном unsigned int. Например:

  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.

Будет ли это относительно быстрая побитовая процедура, которая позволит мне эффективно применить это преобразование (учитывая, что правила трансформации могут измениться)?

Надеюсь, я четко сформулировал свой вопрос. Спасибо за любую помощь.

РЕДАКТИРОВАТЬ: я исправил некоторые ошибки и разъяснил некоторые моменты после комментариев.

РЕДАКТИРОВАТЬ2: Следуя некоторым предложениям, я добавлю, как я надеюсь, пример кода:

#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

Подумав об этом и использовав некоторые идеи из других ответов, я думаю, что нашел общее решение. Он основан на первой оценке значения, предполагая, что есть только ключи 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; 
} 

Answer 2

Это, по сути, проблема упрощения таблиц истинности до минимальных логических выражений; здесь нам нужно два выражения, по одному для каждого бита выходного значения.

BA QP

00 10
01 01
10 01
11 XX

B: бит высокого ключа, A: бит низкого ключа, Q: бит высокого значения, P: бит низкого значения

Используя любой из множества доступных инструментов (включая наш мозг) для минимизации комбинационных логик c цепей, мы получаем выражения

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

Мне понадобится решение для любого произвольного отображения.

Вот пример программы для произвольного отображения отображения. Для каждого из двух битов значения имеется 2 ³ возможных выражений (один и тот же набор для обоих битов); Это следующие выражения:

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

Answer 3

, и я заинтересован в преобразовании целого без знака, следуя приведенным выше правилам (т.е. 2-битные пары должны быть преобразованы в соответствии с правилами: 00-> 10, 01-> 01 и 10-> 01 ), так что я получаю 32-битное целое без знака int

Конечно, это можно сделать, но требуемая последовательность операций будет отличаться для каждого из 27 различных отображений из {0, 1, 2 } до {0, 1, 2}. Некоторые могут быть очень простыми, например, для трех константных отображений, но другие требуют более сложных выражений.

Не выполнив тщательного анализа, я склонен предположить, что отображения, которые не являются ни постоянными, ни перестановками, такие, которые представлены в примере, вероятно, имеют наибольшую минимальную сложность. Все они имеют общие характеристики c, которые два ключа соответствуют одному значению, в то время как другой ключ соответствует другому. Один из способов - не обязательно лучший - подойти к поиску выражения для такого отображения - это сосредоточиться сначала на достижении общего результата, когда два ключа отображаются на одно значение, а другой - на другое, а затем перейти к преобразованию результирующие значения к желаемым, если необходимо.

Для представленного примера, например,

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;

. У этого случая на пару меньше операций, чем у выражения в вашем другом ответе, но я не уверен, что это наименьшее возможное количество операций. На самом деле, если вы готовы принять арифметические c операции в дополнение к побитовым, то вы определенно можете сделать это с меньшим количеством операций:

uint32_t keys = /*...*/;
uint32_t values = 0xAAAAAAAAu
        - (((keys & 0xAAAAAAAAu) >> 1) | (keys & 0x55555555u));

Конечно, в целом Различные операции не все имеют одинаковую стоимость, но целочисленные сложения и вычитания, а также побитовые И, ИЛИ и XOR имеют одинаковую стоимость в большинстве архитектур (см., например, * 1031). *).