number of consecutive ones on the left side of an integer using only bit operations

Question

How do I return the number of consecutive ones on the left side of an integer using only bit operations in C (no if, for, while,etc.)? I'm not sure where to begin for this problem.

//BurstSize(-1) = 32, 
//BurstSize(0xFFF0F0F0) = 12
//Legal: ! ~ & ^ | + << >>
//Max ops: 50
int BurstSize(int a) {
   //code 
}

Answer 1

The following answer reverses the number to do the operation, it doesn't use the % operator, it uses one - sign though:

#include <iostream>

int burstSize(int n) {
    // Reverse the bits
    n = (n & 0x55555555) <<  1 | (n & 0xAAAAAAAA) >>  1; 
    n = (n & 0x33333333) <<  2 | (n & 0xCCCCCCCC) >>  2; 
    n = (n & 0x0F0F0F0F) <<  4 | (n & 0xF0F0F0F0) >>  4; 
    n = (n & 0x00FF00FF) <<  8 | (n & 0xFF00FF00) >>  8; 
    n = (n & 0x0000FFFF) << 16 | (n & 0xFFFF0000) >> 16; 

    // rightmost 0-bit, produces 0 if none (e.g., 10100111 -> 00001000)
    int r = ~n & (n + 1);

    // r - 1 will give us a mask of the consequtive 1s to isolate (e.g., 0100 -> 0011)
    n = (r - 1) & n;

    // Count the bits  
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555); 
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333); 
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F); 
    n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF); 
    n = (n & 0x0000FFFF) + ((n >>16) & 0x0000FFFF);     

    // Return the bit count
    return n;
}

int main() {
    std::cout << burstSize(0x00000000) << std::endl; // 0 
    std::cout << burstSize(0x00010F00) << std::endl; // 0 
    std::cout << burstSize(0x80010F00) << std::endl; // 1     
    std::cout << burstSize(0xF0010F00) << std::endl; // 4
    std::cout << burstSize(0xFFFFFFFE) << std::endl; // 31
    std::cout << burstSize(0xFFFFFFFF) << std::endl; // 32
    return 0;
}

Answer 2

Easiest method: invert the number, then find the most significant bit set. The rest you can do yourself (I am 99% sure this is a homework question, so I am giving a hint only. If you really need more help, ask in the comments and I will expand further).

As for finding the most significant bit set, look at https://stackoverflow.com/a/21413883/1967396

for a fairly efficient method.

update Now for a complete method that finds the most significant bit set (after inverting), and then uses a clever lookup table to convert to actual byte (with a modulo 37 trick that didn't come from me... I found it at http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightModLookup but made a small change so it works for 32 bits set). I include code to test patterns from 0 to 32 bits - seems to work.

#include <stdio.h>

int burstSize(int n) {
 // return number of consecutive bits set
 unsigned int m, r;
 m = ~n;
 m = m | m >> 1;
 m = m | m >> 2;
 m = m | m >> 4;
 m = m | m >> 8;
 m = m | m >> 16;
 m = ((m ^ (m >> 1)) | 0x80000000) & m;
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
  -1, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
  7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
  20, 8, 19, 18
};
r = Mod37BitPosition[m % 37]; // <<<< not sure if this is allowed in your assignment...
return 31 - r; // <<< you could rewrite the LUT so you don't need an operation here. I was lazy.
}

int main(void) {
  printf("%d\n", burstSize(0x00000000));
  printf("%d\n", burstSize(0x80000000));
  printf("%d\n", burstSize(0xC0000000));
  printf("%d\n", burstSize(0xE0000000));
  printf("%d\n", burstSize(0xF0000000));
  printf("%d\n", burstSize(0xF8000000));
  printf("%d\n", burstSize(0xFC000000));
  printf("%d\n", burstSize(0xFE000000));
  printf("%d\n", burstSize(0xFF000000));
  printf("%d\n", burstSize(0xFF800000));
  printf("%d\n", burstSize(0xFFC00000));
  printf("%d\n", burstSize(0xFFE00000));
  printf("%d\n", burstSize(0xFFF00000));
  printf("%d\n", burstSize(0xFFF80000));
  printf("%d\n", burstSize(0xFFFC0000));
  printf("%d\n", burstSize(0xFFFE0000));
  printf("%d\n", burstSize(0xFFFF0000));
  printf("%d\n", burstSize(0xFFFFF800));
  printf("%d\n", burstSize(0xFFFFFC00));
  printf("%d\n", burstSize(0xFFFFFE00));
  printf("%d\n", burstSize(0xFFFFFF00));
  printf("%d\n", burstSize(0xFFFFFFF8));
  printf("%d\n", burstSize(0xFFFFFFFC));
  printf("%d\n", burstSize(0xFFFFFFFE));
  printf("%d\n", burstSize(0xFFFFFFFF));
}

Answer 3

TRY THIS:

unsigned int A=0XFFF0; //your own number
    unsigned int B0=(1 & A)/1;
    unsigned int B1=(2 & A)/2;
    unsigned int B2=(4 & A)/4;
    unsigned int B3=(8 & A)/8;
    unsigned int B4=(16 & A)/16;
    unsigned int B5=(32 & A)/32;
    unsigned int B6=(64 & A)/64;
    unsigned int B7=(128 & A)/128;
    unsigned int B8=(256 & A)/256;
    unsigned int B9=(512 & A)/512;
    unsigned int B10=(1024 & A)/1024;
    unsigned int B11=(2048 & A)/2048;
    unsigned int B12=(4096 & A)/4096;
    unsigned int B13=(8192 & A)/8192;
    unsigned int B14=(16384 & A)/16384;
    unsigned int B15=(32768 & A)/32768;

    int  Result=B15+
                B14*(B15)+
                B13*(B14*B15)+
                B12*(B13*B14*B15)+
                B11*(B12*B13*B14*B15)+
                B10*(B11*B12*B13*B14*B15)+
                B9*(B10*B11*B12*B13*B14*B15)+
                B8*(B9*B10*B11*B12*B13*B14*B15)+
                B7*(B8*B9*B10*B11*B12*B13*B14*B15)+
                B6*(B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B5*(B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B4*(B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B3*(B4*B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B2*(B3*B4*B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B1*(B2*B3*B4*B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15)+
                B0*(B1*B2*B3*B4*B5*B6*B7*B8*B9*B10*B11*B12*B13*B14*B15);

Answer 4

If you use GCC, you could call __builtin_clz() to count leading zeros. Invert the input, then it could be used to count leading ones.

int BurstSize(unsigned a) {
    return __builtin_clz(~a);
}

If you cannot access __builtin_*(), then you can implement the leading zero counting function as in Hacker's Delight:

int nlz4(unsigned x) {
   int y, m, n;

   y = -(x >> 16);      // If left half of x is 0,
   m = (y >> 16) & 16;  // set n = 16.  If left half
   n = 16 - m;          // is nonzero, set n = 0 and
   x = x >> m;          // shift x right 16.
                        // Now x is of the form 0000xxxx.
   y = x - 0x100;       // If positions 8-15 are 0,
   m = (y >> 16) & 8;   // add 8 to n and shift x left 8.
   n = n + m;
   x = x << m;

   y = x - 0x1000;      // If positions 12-15 are 0,
   m = (y >> 16) & 4;   // add 4 to n and shift x left 4.
   n = n + m;
   x = x << m;

   y = x - 0x4000;      // If positions 14-15 are 0,
   m = (y >> 16) & 2;   // add 2 to n and shift x left 2.
   n = n + m;
   x = x << m;

   y = x >> 14;         // Set y = 0, 1, 2, or 3.
   m = y & ~(y >> 1);   // Set m = 0, 1, 2, or 2 resp.
   return n + 2 - m;
}

int BurstSize(unsigned a) {
   return nlz4(~a);
}