посещение всех бесплатных слотов в битфилде

Question

У меня есть массив uint64, и для всех неустановленных битов (0 с) я делаю некоторые оценки.

Оценки не очень дороги, но очень мало битов не установлено. Профилирование говорит, что я трачу много времени на логику «найти следующий неустановленный бит».

Есть ли более быстрый способ (на Core2duo)?

Мой текущий код может пропустить много старших 1:

for(int y=0; y<height; y++) {
  uint64_t xbits = ~board[y];
  int x = 0;
  while(xbits) {
    if(xbits & 1) {
      ... with x and y
    }
    x++;
    xbits >>= 1;
  }
}

(И любая дискуссия о том, как / если SIMD / CUDA-ise это будет интригующей касательной!)

Answer 1

Вариант версии справочной таблицы: Иметь справочную таблицу для следующего неустановленного бита для 8-бит. Проверьте 8-битные блоки и AND в 0xFF, сравните, чтобы увидеть, равен ли результат 0xFF. Если это так, пропустите, иначе посмотрите на стол?

Answer 2

Если вы думаете, что неустановленные биты будут необычными, то, возможно, просто

if (xbits != ((uint64_t)-1))
{
   // regular code goes here
}

будет победой. Таким образом, в общем случае (все биты в слове установлены) вы пропустили бы 64 установленных бита за один раз.