Find out how often can x be divided by 2 without loop in C

Question

I'm looking for a way to find how often I can divide a constant x by two (and not get a remainder) without using loops, recursion or the logarithm. Since this is the same problem as finding the index of the least significant non-zero bit, I am hoping that there is some way to use bitwise operations to do this. Unfortunately I wasn't able to come up with it. Any ideas?

Background: I have a loop that doubles the counter on every iteration until it no longer divides the constant x. I want this loop to be unrolled, but the NVIDIA CUDA compiler isn't smart enough to figure out the number of iterations, so I want to rewrite the loop in such a way that the number of iterations becomes more obvious to the compiler:

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

should become something like

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

Answer 1

This can be directly solved using this code for 32 bit numbers (I take no credit).

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];

Answer 2

You can also do this with pure arithmetic without a lookup table (the De Bruijn sequence approach requires a lookup table), but it's expensive. Here it goes:

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

i is the index of the lowest-set bit in v. The formula is valid for values of v with up to 2000 or so zero bits, much larger than any integer type.

See here for an explanation:

Is there any way to compute the width of an integer type at compile-time?

Answer 3

Do a right shift, then a left shift and check for equality with AND, increment a counter for each time this check is successful.

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;
}

This uses a loop though... I can think of ways of eliminating the loop but it's basically "unfolding" the loop.

Answer 4

This can be easily done with a loop (this might not be 100% correct, so feel free to correct):

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

But I believe this is impossible to do without a loop as you're searching for a bit at an unknown position and thus must check all possible positions.

EDIT Revised based on updated description.

Answer 5

If "pow" does not count as logarithm, here is a way to it for all numbers not just "2". The inverse functions that multiply instead of divide are also included for completeness.

GLSL code:

//://////////////////////////////////////////////////////////://
                                                     //://///://
//: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 Code:

    //: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) ) ); };

Transcribing to C is left as an exercise to the reader.