copenclopencl-c

counting single bits in OpenCL?


I have to implement an algorithm using OpenCL, I have given some numbers to compute the number of following zeros consecutive form a certain offset, for each number. Here is the code:

int count=0;
    for(int i=63-offset; i>=0; i--)
    {
        long long int count_pow_1 = 1;
        long long int base = 2;
        long long int exp = i;
        for(int j=exp; j>=0; j--){
            if(j==0) {break;}
            if(j==1) {count_pow_1 = count_pow_1 * base; break;}
            count_pow_1 = count_pow_1 * base;
        }
        
        unsigned long long int count_pow = count_pow_1;
            
        if(((bits/(count_pow))%2)==1){
            break;
        }else{
            count++;
        }
    }

where count is the number of following zeros. But it doesn't work, it gives me some number near 56 with an offset of 8, which means that the numbers are seen as all zeros or almost all zeros. Do you see where is the problem? Executing the code on CPU not with opencl it seems to work correctly.


Solution

  • You can do this way faster and more elegant: To get the number of following zeros from an offset, first bit-shift the number to the left by the offset (bits = bits<<offset;) and then compute the number of leading zeros.

    To compute the number of leading zeros, you can either use the built-in OpenCL function int count = clz(bits);, see the OpenCL 1.2 reference card. Alternatively, you can leverage that casting to double implicitely does a log2 for the exponent, which is equivalent to the length of the number in bits minus 1 minus the number of leading zeros: int count = 63-(int)((as_ulong((double)bits)>>52)-1023);. clz executes very slowly, so the casting trick runs much faster.