Узнайте, как часто х можно разделить на 2 без цикла в C

Я ищу способ узнать, как часто я могу разделить константу 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 ответа

Решение

Это можно решить напрямую, используя этот код для 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];
Источник

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

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

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

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

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

Источник

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

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

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

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

Источник

Если "pow" не считается логарифмом, вот способ вычисления всех чисел, а не только "2". Обратные функции, которые умножают вместо деления, также включены для полноты.

Код GLSL:

//://////////////////////////////////////////////////////////://
                                                     //://///://
//:IFDO: Move this somewhere more general IF you     //://///://
//:      ever find a need to call it from somewhere  //://///://
//:      else.                                       //://///://
int                                                  //://///://
ES2_AA2_Di2(                                         //://///://
    int B //:BASE:(Affected_Number)                  //://///://
,   int N //:NUMB:(Number_Of_Times_To_Divide_By_Two) //://///://
){                                                   //://///://

    //:programtic_equivalent_of_formula_below:---------------://
    //:                                                      ://
    //:    var b = B;                                        ://
    //:    for( var n = 0; n < N; n++ ){                     ://
    //:        b = b / 2;                                    ://
    //:    };;                                               ://
    //:    return( b /** R **/ );                            ://
    //:______________________________________________________://
  
    int R = int(  float(                  0  )   
        +         float(                  B  )    
        /           pow( float(2) , float(N) )  
    );;
  
    return( R );

    return( int(0) );
}//://////////////////////////////////////////| ES2_AA2_Di2 |://
//://////////////////////////////////////////////////////////://

Код JavaScript:

    //:B: Base                 //: MUL:A_NUMBER_OF_TIMES ://
    //:N: N number of times.   //: MUL:A_NUMBER_OF_TIMES ://
    const AA2_Mu2=( B, N )=>{ return(  B * (pow(2,N) ) ); };
    const AA2_Mu3=( B, N )=>{ return(  B * (pow(3,N) ) ); };
    const AA2_Mu4=( B, N )=>{ return(  B * (pow(4,N) ) ); };
    const AA2_Mu5=( B, N )=>{ return(  B * (pow(5,N) ) ); };
    
    //:B: Base                 //: DIV:A_NUMBER_OF_TIMES ://
    //:N: N number of times.   //: DIV:A_NUMBER_OF_TIMES ://
    const AA2_Di2=( B, N )=>{ return(  B / (pow(2,N) ) ); };
    const AA2_Di3=( B, N )=>{ return(  B / (pow(3,N) ) ); };
    const AA2_Di4=( B, N )=>{ return(  B / (pow(4,N) ) ); };
    const AA2_Di5=( B, N )=>{ return(  B / (pow(5,N) ) ); };

Расшифровка текста на C оставлена ​​читателю в качестве упражнения.

Источник

Сделайте правое смещение, затем левое смещение и проверьте равенство с 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;
}

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

Источник
Другие вопросы по тегам