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

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

方法1：线性时间算法

unsigned int v;  // 需要计算的目标整数

int c;  // c用来保存计算的结果

if (v)

{

  v = (v ^ (v - )) >> ;

  for (c = ; v; c++)

  {

    v >>= ;

  }

}

else

{

  c = CHAR_BIT * sizeof(v);

}

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

#include<stdio.h>

#include<math.h>

#include<limits.h>

void tranlate(long long n)  //十进制转换为二进制

{

    int a[];

    long long i,L,j;

    i=L=;

    while(n/){

        a[i]=n%;

        n/=;

        L++,i++;

    }

    a[i]=;

    while(L<){    //设置为显示32位的二进制

        a[++i]=;

        L++;

    }

    for(j=L-; j>=; j--){

        printf("%d",a[j]);

    }

    printf("\n");

}

int main()

{

    unsigned int v;

    int c;

    v=;

    tranlate(v);

    tranlate(v-);

    tranlate(v^(v-));

    if (v)

    {

      v = (v ^ (v - )) >> ;

      for (c = ; v; c++)

      {

        v >>= ;

      }

    }

    else

    {

      c = CHAR_BIT * sizeof(v);

    }

    printf("%d\n",c);

    getchar();

    return ;

}

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

方法2：并行算法

unsigned int v;      //32位目标数

unsigned int c = ; // c保存结果

v &= -signed(v);

if (v) c--;

if (v & 0x0000FFFF) c -= ;

if (v & 0x00FF00FF) c -= ;

if (v & 0x0F0F0F0F) c -= ;

if (v & 0x33333333) c -= ;

if (v & 0x55555555) c -= ;

这里，我们基本上做了与并行计算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 = ;

}

else

{

  c = ;

  if ((v & 0xffff) == )

  {

    v >>= ;

    c += ;

  }

  if ((v & 0xff) == )

  {

    v >>= ;

    c += ;

  }

  if ((v & 0xf) == )

  {

    v >>= ;

    c += ;

  }

  if ((v & 0x3) == )

  {

    v >>= ;

    c += ;

  }

  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 >> ) - 0x7f;

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

unsigned int v;  // 目标整数

int r;           // r保存结果

static const int Mod37BitPosition[] = //制作一张关于每一个整数对37取模的余数相对应的位置

{

  , , , , , , , , , , , , , , , , ,

  , , , , , , , , , , , , , , , ,

  , , ,

};

r = Mod37BitPosition[(-v & v) % ];

原理：

由于二进制数字尾部连续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[] =

{

  , , , , , , , , , , , , , , , ,

  , , , , , , , , , , , , , , ,

};

r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> ];

巴特西

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

最新文章

热门文章