оптимальный способ найти первый доступный бит

Question

Учитывая массив неисследованных целых чисел (4 октета каждый), каков оптимальный способ найти первый элемент с по крайней мере одним битом 0 и его индексом из LSB.

например: где n = 9

unsinged int uIntArray[] = {
    0xffffffff,
    0xffffffff,
    0xffffffff,
    0xffffffff,
    0xffffff9f,
    0x00000000,
    0x00000000,
    0x00000000,
    0x00000000,
};

Ответы:

element's index = 4
bit's index = 4

Я мог думать только о:

int main (void)
{
    bool found_f = false;
    int n = 9;  //our test case value
    unsigned int uIntArray[] = {
        0xffffffff,
        0xffffffff,
        0xffffffff,
        0xffffffff,
        0xffffff8f,
        0x00000000,
        0x00000000,
        0x00000000,
        0x00000000,
    };  

    unsigned int uIntBits [32] = {
        1, 2, 4, 8, 16, 32, 64, 128,
            256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
            65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
            16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648
    };      

    unsigned int idx, jdx;
    int ele_idx = -1; 
    int bit_idx = -1;

    for (idx =0; idx < n; idx ++) {
        if (uIntArray[idx] < UINT_MAX) { /* our candidate */
            for (jdx =0; jdx < 32; jdx ++)  {
                if ((uIntBits[jdx] & uIntArray[idx])) {
                    ele_idx = idx; 
                    bit_idx = jdx;
                    found_f = true;
                    break;
                }   
            }   
        }   
        if(found_f) {
            break;
        }   
    }   
    fprintf (stderr, "\nEleIdx[%d] BitIdx[%d]\n", ele_idx, bit_idx);
    return 0;
}   

Есть ли лучший способ сделать это?

Answer 1

Индекс наименее значимого 0 в x является индексом наименее значимого 1 в ~x.Чтобы найти последнее, вам нужно просто посчитать конечные нули в ~x.Есть довольно много способов сделать это, см. Здесь http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear

Используя последний метод (основанный на последовательности DeBruijn), поиск будет выглядеть как

static const unsigned MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

for (idx = 0; idx < n; idx ++)
  if (uIntArray[idx] < UINT_MAX)
    break;

if (idx < n) {
  unsigned v = ~uIntArray[idx];
  int bit_idx = MultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531u) >> 27];
  fprintf(stderr, "\nEleIdx[%d] BitIdx[%d]\n", idx, bit_idx);
}

Answer 2

Следующий код, кажется, работает хорошо, используя тест ~x & (x + 1) из другого (теперь удаленного) ответа и расширяя его. Не уверен, почему другой ответ был удален.

/* Return the position of the first clear bit in the array,
 * or -1 if none found.
 *  arr:  array of uint32_t to search
 *  sz:   number of elements in arr
 */
int findClearBit(uint32_t *arr, int sz)
{
  int i;
  for (i = 0; i < sz; i++) {
    if (~arr[i]) {
      switch (~arr[i] & (arr[i] + 1)) {
        case 1 << 31:  return (i * 32) + 31;
        case 1 << 30:  return (i * 32) + 30;
        case 1 << 29:  return (i * 32) + 29;
        case 1 << 28:  return (i * 32) + 28;
        case 1 << 27:  return (i * 32) + 27;
        case 1 << 26:  return (i * 32) + 26;
        case 1 << 25:  return (i * 32) + 25;
        case 1 << 24:  return (i * 32) + 24;
        case 1 << 23:  return (i * 32) + 23;
        case 1 << 22:  return (i * 32) + 22;
        case 1 << 21:  return (i * 32) + 21;
        case 1 << 20:  return (i * 32) + 20;
        case 1 << 19:  return (i * 32) + 19;
        case 1 << 18:  return (i * 32) + 18;
        case 1 << 17:  return (i * 32) + 17;
        case 1 << 16:  return (i * 32) + 16;
        case 1 << 15:  return (i * 32) + 15;
        case 1 << 14:  return (i * 32) + 14;
        case 1 << 13:  return (i * 32) + 13;
        case 1 << 12:  return (i * 32) + 12;
        case 1 << 11:  return (i * 32) + 11;
        case 1 << 10:  return (i * 32) + 10;
        case 1 << 9:   return (i * 32) + 9;
        case 1 << 8:   return (i * 32) + 8;
        case 1 << 7:   return (i * 32) + 7;
        case 1 << 6:   return (i * 32) + 6;
        case 1 << 5:   return (i * 32) + 5;
        case 1 << 4:   return (i * 32) + 4;
        case 1 << 3:   return (i * 32) + 3;
        case 1 << 2:   return (i * 32) + 2;
        case 1 << 1:   return (i * 32) + 1;
        case 1:        return (i * 32);
        default:       return -1;
      }
    }
  }
  return -1;
}

Answer 3

Чтобы найти первый элемент, вы можете заметить, что если число не имеет бит 0, то оно должно быть 0xff..ff, поэтому вместо явной проверки каждого бита вы можете просто сравнить его до 0xff..ff.

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

Answer 4

Вы можете сделать это быстрее, используя большие типы данных.Таким образом, вместо того, чтобы проверять, является ли каждый int 0xffffffff, вы можете использовать 64-битные целые числа и проверять 0xffffffffffffffff.

. Если вы хотите векторизовать, вы можете выполнить 128-бит (SSE) или 256 бит (AVX) одновременно.

Во всех случаях следите за выравниванием данных.Если вы не выровняете, он либо не будет работать, либо замедлится.

Чтобы сделать последний шаг, вы можете развернуть цикл и проверить несколько слов / векторов за раз.Это даст вам лучший IPC.Только когда вы находите какой-либо ноль, вы проходите путаницу сужения того, какой это бит.

РЕДАКТИРОВАТЬ:

Чтобы проиллюстрировать этот последний момент, вы можете сделать это: (Я опущенкод очистки в случае idx % 4 != 0)

for (idx =0; idx < n; idx += 4) {
    unsigned int test = uIntArray[idx];
    test &= uIntArray[idx + 1];
    test &= uIntArray[idx + 2];
    test &= uIntArray[idx + 3];

    if (test < UINT_MAX){
        //  Find which bit it is.

    }
}

За исключением того, что вы можете сделать это для больших типов данных.(например, векторы SSE / AVX)

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