Вопрос битовой операции - PullRequest
Новая
       14

Вопрос битовой операции

6 голосов
/ 05 июня 2011

Есть ли способ найти бит, который был установлен наименьшее количество раз, используя только битовые операции?

Например, если у меня есть три битовых массива: 

11011001

11100000  
11101101

, биты в позициях 3 и 5 установлены в 1 только в 1 из трех векторов.

В настоящее время у меня есть решение o(n), где n - это число бит в битовой матрице, где я перебираю каждый бит в битовой матрице и увеличиваю каждый раз, когда есть 1, но по какой-то причине я думаю,o(1) решение, которое я могу использовать с несколькими побитовыми операциями.Кто-нибудь может посоветовать?Благодаря.

Ответы [ 5 ]

4 голосов
/ 05 июня 2011

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

Например, для каждого "битов«8-битное значение, при условии, что не более 15 значений: 

bits1 = (bits >> 3) & 0x11;
bits2 = (bits >> 2) & 0x11;
bits3 = (bits >> 1) & 0x11;
bits4 = bits & 0x11;
bitsSum1 += bits1;
bitsSum2 += bits2;
bitsSum3 += bits3;
bitsSum4 += bits4;

Затем, в конце, разбить каждое значение bitsSumN на два 4-битных значения.

3 голосов
/ 05 июня 2011

Другой вариант - отразить битовый массив. В вашем примере: 

111
111
011
100
101
001
000
101

А затем используйте стандартные методы подсчета битов для подсчета количества установленных битов.

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

1 голос
/ 05 июня 2011

если у вас будет 16 или меньше массивов, обрабатывайте битовые комбинации как шестнадцатеричные числа (вместо двоичных) и просто складывайте их вместе.но я боюсь, что это все равно будет менее эффективно, чем ваше решение o (n).(и да, я понимаю, что добавление не является побитовой операцией.)

0 голосов
/ 02 января 2014

Стоит отметить, что если в каждом бите будет добавлено некоторое количество начальных нулей, то при добавлении всех входных значений будет получен битовый счетчик каждого, нам просто нужно его замаскировать или что-то в этом роде, чтобы получить его. Тогда сам подсчет битов становится тривиальным, но возникают другие вопросы, такие как:

  • Как мне преобразовать мой ввод в формат, в котором я хотел бы работать?
  • Как получить счетчик битов после выполнения операции?
  • Должен ли я хранить свои данные в преобразованном формате?
  • Какое максимальное количество битов?

В приведенном ниже коде я решил поддерживать максимальный счетчик битов 15, но он может быть легко расширен до 255. Я решил рассмотреть только правильно сформированные входные данные для функции (без пустых или слишком больших входных массивов). И даже если сборка, сгенерированная вызывающей стороной для доступа к битовым полям, вероятно, будет включать некоторые сдвиги или маски, это нормально.

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

struct BitCount
{
    unsigned char bit0 : 4;
    unsigned char bit1 : 4;
    unsigned char bit2 : 4;
    unsigned char bit3 : 4;
    unsigned char bit4 : 4;
    unsigned char bit5 : 4;
    unsigned char bit6 : 4;
    unsigned char bit7 : 4;
    unsigned char bit8 : 4;
    unsigned char bit9 : 4;
    unsigned char bitA : 4;
    unsigned char bitB : 4;
    unsigned char bitC : 4;
    unsigned char bitD : 4;
    unsigned char bitE : 4;
    unsigned char bitF : 4;
};

void CountBits(const short *invals, unsigned incount, BitCount &bitcount)
{
    assert(incount && incount <= 0xF && sizeof bitcount == 8);
    static const unsigned expand[256] = {
        //      _0          _1          _2          _3          _4          _5          _6          _7          _8          _9          _A          _B          _C          _D          _E          _F
        0x00000000, 0x00000001, 0x00000010, 0x00000011, 0x00000100, 0x00000101, 0x00000110, 0x00000111, 0x00001000, 0x00001001, 0x00001010, 0x00001011, 0x00001100, 0x00001101, 0x00001110, 0x00001111,   // 0_
        0x00010000, 0x00010001, 0x00010010, 0x00010011, 0x00010100, 0x00010101, 0x00010110, 0x00010111, 0x00011000, 0x00011001, 0x00011010, 0x00011011, 0x00011100, 0x00011101, 0x00011110, 0x00011111,   // 1_
        0x00100000, 0x00100001, 0x00100010, 0x00100011, 0x00100100, 0x00100101, 0x00100110, 0x00100111, 0x00101000, 0x00101001, 0x00101010, 0x00101011, 0x00101100, 0x00101101, 0x00101110, 0x00101111,   // 2_
        0x00110000, 0x00110001, 0x00110010, 0x00110011, 0x00110100, 0x00110101, 0x00110110, 0x00110111, 0x00111000, 0x00111001, 0x00111010, 0x00111011, 0x00111100, 0x00111101, 0x00111110, 0x00111111,   // 3_
        0x01000000, 0x01000001, 0x01000010, 0x01000011, 0x01000100, 0x01000101, 0x01000110, 0x01000111, 0x01001000, 0x01001001, 0x01001010, 0x01001011, 0x01001100, 0x01001101, 0x01001110, 0x01001111,   // 4_
        0x01010000, 0x01010001, 0x01010010, 0x01010011, 0x01010100, 0x01010101, 0x01010110, 0x01010111, 0x01011000, 0x01011001, 0x01011010, 0x01011011, 0x01011100, 0x01011101, 0x01011110, 0x01011111,   // 5_
        0x01100000, 0x01100001, 0x01100010, 0x01100011, 0x01100100, 0x01100101, 0x01100110, 0x01100111, 0x01101000, 0x01101001, 0x01101010, 0x01101011, 0x01101100, 0x01101101, 0x01101110, 0x01101111,   // 6_
        0x01110000, 0x01110001, 0x01110010, 0x01110011, 0x01110100, 0x01110101, 0x01110110, 0x01110111, 0x01111000, 0x01111001, 0x01111010, 0x01111011, 0x01111100, 0x01111101, 0x01111110, 0x01111111,   // 7_
        0x10000000, 0x10000001, 0x10000010, 0x10000011, 0x10000100, 0x10000101, 0x10000110, 0x10000111, 0x10001000, 0x10001001, 0x10001010, 0x10001011, 0x10001100, 0x10001101, 0x10001110, 0x10001111,   // 8_
        0x10010000, 0x10010001, 0x10010010, 0x10010011, 0x10010100, 0x10010101, 0x10010110, 0x10010111, 0x10011000, 0x10011001, 0x10011010, 0x10011011, 0x10011100, 0x10011101, 0x10011110, 0x10011111,   // 9_
        0x10100000, 0x10100001, 0x10100010, 0x10100011, 0x10100100, 0x10100101, 0x10100110, 0x10100111, 0x10101000, 0x10101001, 0x10101010, 0x10101011, 0x10101100, 0x10101101, 0x10101110, 0x10101111,   // A_
        0x10110000, 0x10110001, 0x10110010, 0x10110011, 0x10110100, 0x10110101, 0x10110110, 0x10110111, 0x10111000, 0x10111001, 0x10111010, 0x10111011, 0x10111100, 0x10111101, 0x10111110, 0x10111111,   // B_
        0x11000000, 0x11000001, 0x11000010, 0x11000011, 0x11000100, 0x11000101, 0x11000110, 0x11000111, 0x11001000, 0x11001001, 0x11001010, 0x11001011, 0x11001100, 0x11001101, 0x11001110, 0x11001111,   // C_
        0x11010000, 0x11010001, 0x11010010, 0x11010011, 0x11010100, 0x11010101, 0x11010110, 0x11010111, 0x11011000, 0x11011001, 0x11011010, 0x11011011, 0x11011100, 0x11011101, 0x11011110, 0x11011111,   // D_
        0x11100000, 0x11100001, 0x11100010, 0x11100011, 0x11100100, 0x11100101, 0x11100110, 0x11100111, 0x11101000, 0x11101001, 0x11101010, 0x11101011, 0x11101100, 0x11101101, 0x11101110, 0x11101111,   // E_
        0x11110000, 0x11110001, 0x11110010, 0x11110011, 0x11110100, 0x11110101, 0x11110110, 0x11110111, 0x11111000, 0x11111001, 0x11111010, 0x11111011, 0x11111100, 0x11111101, 0x11111110, 0x11111111 }; // F_
    unsigned *const   countLo = (unsigned*)&bitcount;
    unsigned *const   countHi = (unsigned*)&bitcount + 1;
    *countLo = expand[*invals & 0xFF];
    *countHi = expand[*invals++ >> 8];
    switch (incount)
    {
        case 0xF:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0xE:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0xD:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0xC:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0xB:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0xA:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0x9:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0x8:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0x7:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0x6:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0x5:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0x4:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0x3:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals++ >> 8];
        case 0x2:
            *countLo += expand[*invals & 0xFF];
            *countHi += expand[*invals >> 8];
    };
}

РЕДАКТИРОВАТЬ Вы можете пропустить приведенный выше поиск таблиц в 64-битной системе, если увеличите значения счетчика битов с 4 до 8 бит, используя преимущества свойств умножения.

Это интересующее нас свойство (a, b, c и d равны 0 или 1, а n - двоичное число):
n * (a * 2 ^ 3 + b * 2 ^ 2 + c * 2 ^ 1 + d * 2 ^ 0) <=> ((a * n) << 3) + ((b * n) << 2 ) + ((c * n) << 1) + ((d * n) << 0) </p>

Таким образом, если мы приведем байт к 64-битному целому числу и тщательно выберем множитель, мы можем получить 0 или 1 в первом бите каждого байта продукта. Вот такой множитель:

00000000 00000010 00000100 00001000 00010000 00100000 01000000 10000001
или 0x002040810204081

Итак, мы можем расширить байт до 64 битов так: 

unsigned char b = ...

// this operation can be used in substitution of the below look-up table
// (if the code is written for 8-bit wide count, instead of 4-bit wide counts)
unsigned __int64 valx = ((unsigned __int64)b * 0x002040810204081) & 0x0101010101010101;

Затем мы можем извлечь количество битов, подобных этому, в системах с прямым порядком байтов 

union ResultType {
  unsigned __int64 result;
  unsigned char    bitcount[8]; // bitcount[x] is the number of times the x-th most significant bit appeared
};

ResultType r;
r.result = val1 + val2 + val3 + ...; // up to 255 values can be summed before we risk overflow

r.bitcount[2] // how many times the 00000100 bit was set
0 голосов
/ 05 июня 2011

Если у вас будет 15 предметов или меньше, я бы посоветовал вам начать с разделения каждой группы из трех чисел на две, а затем каждой группы из пятнадцати на четыре. Что-то вроде: 

  uint32 x0,y0,z0,x1,y1,z1, ... x4,y4,z4; // Input values
  uint32 even0,even1,...even4,odd0...odd4;
  uint lowereven,lowerodd,uppereven,upperodd;

  even0 = (x0 & 0x55555555) + (y0 & 0x55555555) + (z0 & 0x555555555);
  odd0 = ((x0>>1) & 0x55555555) + ((y0>>1) & 0x55555555) + ((z0>>1) & 0x555555555);
  ... then do likewise for even1...even4 and odd1...odd4

  lowereven = ((even0 & 0x333333333) + (even1 & 0x33333333) + (even2 & 0x33333333)...;
  lowerodd = ((even0 & 0x333333333) + (even1 & 0x33333333) + (even2 & 0x33333333)...;
  uppereven = ((even0 >> 2) & 0x33333333) + ((even1 >> 2) & 0x33333333) + ...;
  oddeven = ((odd0 >> 2) & 0x33333333) + ((odd1 >> 2) & 0x33333333) + ...;

После этих операций четыре значения будут содержать количество бит для всех битов. LowerEven будет хранить количество битов 0, 4, 8, 16 и т. Д .; LowerOdd содержит 1, 5, 9 и т. Д .; UpperEven содержит 2, 6, 10 и т. Д .; UpperOdd содержит 3, 7, 11 и т. Д.

Если бы у одного было более 15 чисел, можно обработать до 255 чисел в группах по 15, выполнив вышеуказанное для каждой группы, а затем используя восемь операторов для объединения всех групп.

...