C语言中的位操作（16）--计算二进制数字尾部连续0的数目

本篇文章介绍计算二进制数字尾部连续0的数目的相关算法，例如：v=(1101000)₂,该数尾部连续0的数目=3

方法1：线性时间算法

unsigned int v;  // 需要计算的目标整数
int c;  // c用来保存计算的结果
if (v)
{
  v = (v ^ (v - 1)) >> 1;  
  for (c = 0; v; c++)
  {
    v >>= 1;
  }
}
else
{
  c = CHAR_BIT * sizeof(v);
}

原理比较简单，下面提供一段C测试代码，根据代码显示的结果不难理解算法:

#include<stdio.h>
#include<math.h>
#include<limits.h>

void tranlate(long long n)  //十进制转换为二进制
{
    int a[1000];
    long long i,L,j;
    i=L=0;
    while(n/2){
        a[i]=n%2;
        n/=2;
        L++,i++;
    }
    a[i]=1;
    while(L<32){    //设置为显示32位的二进制
        a[++i]=0;
        L++;
    }
    for(j=L-1; j>=0; j--){
        printf("%d",a[j]);
    }
    printf("
");
}

int main()
{
    unsigned int v;
    int c;  
    v=12;
    tranlate(v);
    tranlate(v-1);
    tranlate(v^(v-1));
    if (v)
    {
      v = (v ^ (v - 1)) >> 1; 
      for (c = 0; v; c++)
      {
        v >>= 1;
      }
    }
    else
    {
      c = CHAR_BIT * sizeof(v);
    }

    printf("%d
",c);
    getchar();
    return 0;
}

对于一个随机的二进制数而言，尾部连续为0的数目平均值为1，于是上面这个算法相比下面较快的算法不算很糟

方法2：并行算法

unsigned int v;      //32位目标数
unsigned int c = 32; // c保存结果
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

这里，我们基本上做了与并行计算log2（N）类似的操作，但是我们首先分隔开最低位，然后将c保存最大值并且逐渐递减，对于N位数操作大致不会超过3*lg(N)+4

原理：

若v=A₃₂……A_i100……0,

执行v&=-signed(v)操作， v=0……0100……0，若v！=0，则v中一定至少含1位非0，c--

然后通过下面的5步分别判断，逐步缩小范围，最后得到的结果保存在c中

方法3：二分查找算法

unsigned int v;   //目标32位整数
unsigned int c;  //c保存结果  
             // 注意:假如 0 == v, 则 c = 31.
if (v & 0x1) 
{
  // 特别地，当v为奇数的时候（假设会发生,有一半的概率）
  c = 0;
}
else
{
  c = 1;
  if ((v & 0xffff) == 0) 
  {  
    v >>= 16;  
    c += 16;
  }
  if ((v & 0xff) == 0) 
  {  
    v >>= 8;  
    c += 8;
  }
  if ((v & 0xf) == 0) 
  {  
    v >>= 4;
    c += 4;
  }
  if ((v & 0x3) == 0) 
  {  
    v >>= 2;
    c += 2;
  }
  c -= v & 0x1;
}

这个算法与前面介绍过的算法类似，但是它计算尾部连续0的个数采用一种跳跃式的二分查找

首先，检测最低的16位是否为0，如果是，将v向右移动16位并且c+=16，这样就成半的减少了v中符合条件的比特位，每一个接着的步骤进行类似的二分操作直到剩下1。

方法4：通过float型转换

unsigned int v;            // 目标整数
int r;                     // r 保存结果
float f = (float)(v & -v); // 将v的最低有效位强制转化为float型
r = (*(uint32_t *)&f >> 23) - 0x7f;

方法5：通过模除法与查表

unsigned int v;  // 目标整数
int r;           // r保存结果
static const int Mod37BitPosition[] = //制作一张关于每一个整数对37取模的余数相对应的位置
{
  32, 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[(-v & v) % 37];

原理：

由于二进制数字尾部连续0的数目与该二进制的最低有效位的位置有关，而最低有效位的位置只可能出现在0~31的位置，相应的值为0~32，规定当v=0时，r=32

以上的代码作用是计算给定二进制数字尾部连续0的数目，于是对于二进制数0100，结果为2，以上算法基于以下事实：开始的32位位置相对而言与37互素，于是执行模37得到介于0~36之间唯一的一个数字，这些数字可以用来通过查表匹配连续0的数目

方法6：通过模与查表

unsigned int v;  
int r;           
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];