Узнайте, как часто можно разделить x на 2 без цикла в C - PullRequest
1 голос
/ 18 февраля 2011

Я ищу способ узнать, как часто я могу делить константу x на два (и не получать остаток) без использования циклов, рекурсии или логарифма. Поскольку это та же проблема, что и при поиске индекса младшего значащего ненулевого бита, я надеюсь, что для этого есть способ использовать побитовые операции. К сожалению, я не смог придумать это. Есть идеи?

Справочная информация: у меня есть цикл, который удваивает счетчик на каждой итерации, пока он больше не делит константу х. Я хочу, чтобы этот цикл был развернут, но компилятор NVIDIA CUDA недостаточно умен, чтобы вычислить количество итераций, поэтому я хочу переписать цикл таким образом, чтобы число итераций стало более очевидным для компилятора:

for(i=1; CONST & i == 0; i *= 2)
     bla(i);

должно стать чем-то вроде

#define ITERATIONS missing_expr_with_CONST
for(i=0; i < ITERATIONS; i++)
     fasel(i);

Ответы [ 4 ]

7 голосов
/ 18 февраля 2011

Это можно решить напрямую, используя этот код для 32-битных чисел (я не беру кредит).

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int 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
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
3 голосов
/ 18 февраля 2011

Вы также можете сделать это с помощью чистой арифметики без справочной таблицы (подход последовательности Де Брюйна требует справочную таблицу), но это дорого. Вот оно:

m = (v&-v)-1;
i = ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12));

i - это индекс младшего установленного бита в v. Формула действительна для значений v, содержащих до 2000 или около того нулевых битов, намного больше, чем любой целочисленный тип.

Смотрите здесь для объяснения:

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

0 голосов
/ 18 февраля 2011

Это легко сделать с помощью цикла (это может быть не на 100% правильно, поэтому не стесняйтесь исправлять):

int leastSigBit(int num) {
  int result;
  for(result = 0; num & 1 != 1; ++result)
    num >>= 1;
  return result;
}

Но я считаю, что это невозможно без цикла, как выповторный поиск в неизвестной позиции и, следовательно, должен проверить все возможные позиции.

РЕДАКТИРОВАТЬ Пересмотрено на основе обновленного описания.

0 голосов
/ 18 февраля 2011

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

int powerOfTwo(int x) {
    int counter = 0;
    while(x > 0) {
        int y = x >> 1;
        y <<= 1;
        if(x ^ y) {
            counter++;
        } else {
            break;
        }
        x >>= 1;
    }
    return counter;
}

Хотя здесь используется цикл ... Я могу подуматьспособов устранения цикла, но в основном это «развертывание» цикла.

...