Две операции над массивом битов в C / C ++

Question

// b: uint32_t array of size n    => 32*n bits
// The bit index, i, is in the range 0 <= i < 32 * n
// The bit in b at bit index 0 is always 0!

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) {
    // Returns a bit index, k, such that k <= i and k is the largest bit index
    // for which bit k in b is 0.
}

// As above, value == 0 or 1
void set_bit (uint32_t *b, unsigned n, unsigned i, unsigned value) {
    // Sets bit at bit index i to value.
    // It could be something like (untested):
    if (value)
        b[i >> 5] |=   (1 << (i&31));
    else
        b[i >> 5] &= (~(1 << (i&31)));
}

Я ищу наиболее эффективный, но все же переносимый (для разных целей, но используется только компилятор g ++) способ реализации этих функций (особенно первой).Порядок хранения битов (big, little endian или что-то еще) не имеет значения.

Наивная реализация (не проверено):

uint32_t get_bit (uint32_t *b, unsigned n, unsigned i) {
    return b[i >> 5] & (1 << (i&31));
}

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) {
    while (get_bit (b, n, i)) 
        i--;
    return i;
}

Пропуск всех элементов 1:

unsigned idx_of_first_zero_bit_before_or_at (uint32_t *b, unsigned n, unsigned i) {
    for (unsigned k = i >> 5; ~(b[k]) == 0; i = (--k << 5) + 31);
    while (get_bit (b, n, i)) 
        i--;
    return i;
}

Answer 1

В зависимости от того, сколько памяти у вас есть, вы можете выбрать подход из таблицы поиска.Например, если вы можете потратить 256 байтов, то следующая функция сделает это за один uint32_t:

static const int table[256] = { 
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
    3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 0, 0,
};


int func(uint32_t b, int i)
{
    b = (b << (31-i));

    if ((b & 0xFFFF0000) != 0xFFFF0000)
    {
        return ((b & 0xFF000000) != 0xFF000000)
             ? table[(b >> 24) & 0xFF] + 24 - (31-i)
             : table[(b >> 16) & 0xFF] + 16 - (31-i);
    }
    else
    {
        return ((b & 0xFF00) != 0xFF00)
             ? table[(b >> 8) & 0xFF] + 8 - (31-i)
             : table[(b >> 0) & 0xFF] + 0 - (31-i);
    }
}

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

Если у вас доступно 64 КБ, то вы делаете это для 16-битных блоков одновременнои так далее.Конечно, использование произвольного доступа на большом столе может привести к эффектам кэширования, поэтому вам нужно будет поэкспериментировать и составить профиль.

Answer 2

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

unsigned idx_of_first_zero_bit(uint32_t n) {
  int idx = 0;
  if (n == 0xffffffff) return 32;  // Not found; presumably the common case

  // Binary search
  if (n & 0xffff == 0xffff) {
    n >>= 16;
    idx += 16;
  }
  if (n & 0xff == 0xff) {
    n >>= 8;
    idx += 8;
  }
  if (n & 0xf == 0xf) {
    n >>= 4;
    idx += 4;
  }
  if (n & 0x3 == 0x3) {
    n >>= 2;
    idx += 2;
  }
  if (n & 0x1 == 0x1) {
    n >>= 1;
    idx += 1;
  }
  return idx;
}

Чтобы избежать ошибочных прогнозов ветвлений, вы можете выполнять условное обновление с помощью побитовых операций.

int shift;

// First step
shift = ((n & 0xffff == 0xffff) << 4); // shift = (n & 0xffff == 0xffff) ? 16 : 0
n >>= shift;
idx += shift;

// Next step
shift = ((n & 0xff == 0xff) << 3); // shift = (n & 0xff == 0xff) ? 8 : 0
n >>= shift;
idx += shift;

Answer 3

Обычно я стараюсь избегать «случайных» веток. Например, мы можем взять решение, предложенное Оли Чарльзуортом, и избавиться от if s.

Он решает большинство вычислений с LUT , но для последней части все еще требуются ветви. Введите дополнительный LUT для работы с ним:

unsigned index2 = table[ b        & 0xFF]        |  // Values 0..7, so we use 3 bits
                 (table[(b >>  8) & 0xFF] << 3 ) |  // Next 3 bits..
                 (table[(b >> 16) & 0xFF] << 6 ) |
                 (table[(b >> 24) & 0xFF] << 9 );

Теперь у нас есть 12-битное значение в index2, которое мы можем преобразовать в значимое значение с помощью одного просмотра таблицы:

return table2[index2]; // char[4096] array with precomputed values.

Кроме того, используя в первую очередь 16-разрядную LUT, мы получим два 16-разрядных и 8-разрядный.