Поиск битов в битборде

Мне для покера нужно реализовать поиск бита в битборде. Вроде у нас тут есть парочка спецов по битбордам. Чего посоветуете?

Вот самый простой вариант, как мне кажется:

Code:

int FirstBit8[256];

void InitFirstBit()
{
    for (int i = 0; i < 256; i++)
    {
        int p = i;
        FirstBit8[i] = 0;
        for (int j = 0; j < 8; j++)
        {
            if (p & 1)
            {
                FirstBit8[i] = j;
                break;
            }
            p >>= 1;
        }
    }
}

int ExtractBit(uint64 v)
{
    unsigned char *p = (unsigned char*)&v;
    for (int i = 0; i < 8; i++)
    {
        if (p[i])
        {
            int n = FirstBit8[p[i]];
            p[i] &= ~(1 << n);
            return i * 8 + n;
        }
    }
    return 0;
}

Можно еще перейти на 16-битный массив. Есть ли какие принципиально иные подходы?

 

Вот самый простой вариант для поиска наименьшего (самого правого) установленного бита, с одновременной установкой его в ноль:

Code:

static const FLD LSB_Magic[64] = 
{
   A8, B4, E1, H5, E8, B2, E2, G5,
   D8, H4, F7, G2, A7, E3, C3, F5,
   C8, C4, F1, C7, E7, A3, G6, F3,
   H8, D4, G1, E6, B6, E4, H1, E5,
   B8, A4, F8, D1, C1, G7, B7, B1,
   A2, D7, D2, H6, A1, F6, C6, H3,
   G4, G8, H7, C2, F2, A5, H2, D6,
   D3, A6, B5, B3, G3, C5, D5, F4
};

#define pop_lsb(x)  pop_lsb_inner(&x)

static inline FLD pop_lsb_inner(U64* pb)
{
   if (*pb == 0)
      return NF;

   U64 lsb = *pb ^ (*pb - 1);
   unsigned int foldedLSB = ((int) lsb) ^ ((int)(lsb>>32));
   int ind = (foldedLSB * 0x78291ACF) >> (32-6); // range is 0..63

   *pb &= ~lsb;
   return LSB_Magic[ind];
}

Эта функция не использует ни одной условной операции (ну ладно, только одну - но зато самую часто срабатывающую), требует не очень много дорогих 64-битных операций, и работает практически так же быстро, как и ассемблерные реализации - но при этом написана на чистом Си!

 

Вообще, на эту тему очень много написано и на WB-форуме, например:
http://wbforum.vpittlik.org/viewtopic.php?t=3141

Ну, или в локальный поиск WB-форума - по запросам LSB, FirstOne, magic, de Bruijn и т.п.

 

Мне кажется более интересным попробовать использовать BSR и BSF. Только покажите как в Си делать ассемблерные вставки (я никогда этм не занимался).

Кстати, есть инфа о том, насколько быстро работают BSR и BSF?

 

Несколько лет назад я пробовал - выигрыш в скорости поиска от ассемблерной реализации порядка единиц процентов. Иногда и вообще ноль.

Отказался из-за проблем с портированием, не хотелось для разных компиляторов писать разные функции - у gcc синтаксис ассемблера AT&T, а у MSVC - интеловский. Опять же, юниксовые версии могут вообще на какой-нибудь Альфе запускаться. В общем, получилось бы как у Крафти, универсально, но развесисто и нечитаемо

 

Деление должно быть медленней

 

Ладно, я посмотрю как на скорости скажется переход от 8 бит к 16. И тогда будет видно стоит ли это дальнейших оптимизаций.

 

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

 

Всем хорош такой код, только вот при попытке заинлайнить эту функцию компилятор (gcc, во всяком случае) начинает ругаться на повторное определение метки l: