c - 仅使用位运算的整数左侧连续的个数

Question

如何仅使用 C 中的位运算(没有 if、for、while 等)返回整数左侧连续 1 的个数？我不确定从哪里开始解决这个问题。

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

Answer 1

如果您使用 GCC，您可以调用 __builtin_clz() 来计算前导零。反转输入，然后它可以用来计算领先的。

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

如果您无法访问__builtin_*()，那么您可以实现前导零计数功能，如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);
}