计算一个无符整数中1Bit的个数(1)

2024-06-05 12:48
文章标签 计算 个数 整数 1bit 无符

本文主要是介绍计算一个无符整数中1Bit的个数(1)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转自：http://blog.chinaunix.net/uid-21275705-id-224360.html

Count the number of bits that are on in an unsigned integer（计算一个无符整数中1Bit的个数）-- (1)

计算一个无符号整数中有多少的Bit为1

这是一个经常遇到的经典问题，这里分两个部分讲解和总结，首先对讲解现有的算法，然后再讲解一些改进算法。

1．循环法（Iterated Count）

int bitcount (unsigned int n)  
{
int count=0;      
    while (n)  {
        count += n & 0x1u ;
        n >>= 1 ;
      }
return count ;
}

最容易理解和想到的方法。对每一位依次判断是否为1，如果是就在count上加1。

循环的次数是常数（n的位数）。在1比较稀疏的时候效率低，可用方法2改进。

2．Bit1稀疏Sparse Ones

int bitcount (unsigned int n)  
{
int count=0 ;
         while (n)  {
         count++ ;
         n &= (n - 1) ;
     }
     return count ;
}

理解这个算法的核心，只需理解2个操作：

1> 当一个数被减 1 时，他最右边的那个值为 1 的 Bit 将变为 0 ，同时其右边的所有的 Bit 都会变成 1 。
2>“ &= ”，位与并赋值操作。去掉已经被计数过的 1 ，并将改值重新设置给 n.

这个算法循环的次数是bit位为一的个数。也就说有几个Bit为1，循环几次。对Bit为1比较稀疏的数来说，性能很好。如：0x1000 0000, 循环一次就可以。

3．密集1的算法 Dense Ones

   int bitcount (unsigned int n)    

   {

      int count = 8 * sizeof(int) ;

      n ^= (unsigned int) -1 ;

      while (n)

      {

         count-- ;

         n &= (n - 1) ;

      }

      return count ;

   }

与2稀疏1的算法相类似。不同点是，针对1密集的情况，循环的次数会大大减少。他的循环次数：sizeof(int)-Bit 1的个数。

4．8bit静态表查找法 Precompute_8bit

     static int bits_in_char [256] = {          

    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,

    3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,

    3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,

    4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,

    3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,

    6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,

    4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,

    6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,

    3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,

    4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,

6, 7, 6, 7, 7, 8

};

 
 
     int bitcount (unsigned int n)
     {
        // works only for 32-bit ints
        return bits_in_char [n           & 0xffu]
            +  bits_in_char [(n >>  8) & 0xffu]
            +  bits_in_char [(n >> 16) & 0xffu]
            +  bits_in_char [(n >> 24) & 0xffu] ;
     }

使用静态数组表，列出所有8bit(256个)无符号数含有Bit1的个数。将32Bit 的n分4部分，直接在表中找到对应的Bit1的个数，然后求和。

这是最快的方法了。缺点是需要比较大的内存。

  

5．16bit静态表查找法Precompute_16bit

因为在计算64位int时，以上方法4并不总是最快，所以有以下的一个进化版，就是用十六Bit的表来作驱动映射。这样需要的内存就更大了。

static char bits_in_16bits [0x1u << 16] …;

  int bitcount (unsigned int n)
  {
       // works only for 32-bit ints
       return bits_in_16bits [n           & 0xffffu]
           +  bits_in_16bits [(n >> 16) & 0xffffu] ;
  }

6. 合并计数器法 Parallel Counter

unsigned numbits(unsigned int i)

{
 
      unsigned int const MASK1  = 0x55555555;
      unsigned int const MASK2  = 0x33333333;
      unsigned int const MASK4  = 0x0f0f0f0f;
      unsigned int const MASK8  = 0x00ff00ff;
unsigned int const MASK16 = 0x0000ffff;
/*
MASK1  = 01010101010101010101010101010101
MASK2  = 00110011001100110011001100110011
MASK4  = 00001111000011110000111100001111
MASK8  = 00000000111111110000000011111111
MASK16 = 00000000000000001111111111111111
*/
 
      
    i = (i&MASK1 ) + (i>>1 &MASK1 );
      i = (i&MASK2 ) + (i>>2 &MASK2 );
      i = (i&MASK4 ) + (i>>4 &MASK4 );
      i = (i&MASK8 ) + (i>>8 &MASK8 );
      i = (i&MASK16) + (i>>16&MASK16);
      
    return i;
}

这个算法是一种合并计数器的策略。把输入数的32Bit当作32个计数器，代表每一位的1个数。然后合并相邻的2个“计数器”，使i成为16个计数器，每个计数器的值就是这2个Bit的1的个数；继续合并相邻的2个“计数器“，使i成为8个计数器，每个计数器的值就是4个Bit的1的个数。。依次类推，直到将i变成一个计数器，那么它的值就是32Bit的i中值为1的Bit的个数。

举个例子，假设输入的i值为10010111011111010101101110101111（十进制2541575087）

计算过程如下：（共22个1）

1.        将32个计数器合并为16个,每一个计数器代表 2-bit 的1个数

1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 = 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1

+0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 = 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1

----------------------------------------------------------------------

1 1 1 2 1 2 2 1 1 1 1 2 1 1 2 2 = 01 01 01 10 01 10 10 01 01 01 01 10 01 01 10 10

2.        将16个计数器合并为8个,每一个计数器代表 4-bit 的1个数

1 1 1 2 1 1 1 2 =   01   01   01   10   01   01   01   10

+1 2 2 1 1 2 1 2 =   01   10   10   01   01   10   01   10

---------------   ---------------------------------------

2 3 3 3 2 3 2 4 = 0010 0011 0011 0011 0010 0011 0010 0100

3.        将8个计数器合并为4个,每一个计数器代表 8-bit 的1个数

3 3 3 4 =     0010     0011     0010     0010

+2 3 2 2 =     0011     0011     0011     0100

-------   -----------------------------------

5 6 5 6 = 00000101 00000110 00000101 00000110

4.        将4个计数器合并为2个,每一个计数器代表 16-bit 的1个数

5 5 =         00000101         00000101

+ 6 6 =         00000110         00000110

-----   ---------------------------------

11 11 = 0000000000001011 0000000000001011

5.        最后，将2个计数器合并为1个,每一个计数器代表 32-bit （也就是输入的值i）的1个数

11 =                 0000000000001011

+11 =                 0000000000001011

--   --------------------------------

22 = 00000000000000000000000000010110

对于该算法的实现，另外有一种比较好的写法，这种算法避免了使用常数宏，使比较通用的实现：

  #define TWO(c)       (0x1u << (c))
  #define MASK(c)      (((unsigned int)(-1)) / (TWO(TWO(c)) + 1u))
  #define COUNT(x,c) ((x) & MASK(c)) + (((x) >> (TWO(c))) & MASK(c))
  int bitcount (unsigned int n)
  {
       n = COUNT(n, 0) ;
       n = COUNT(n, 1) ;
       n = COUNT(n, 2) ;
       n = COUNT(n, 3) ;
       n = COUNT(n, 4) ;
       /* n = COUNT(n, 5) ;      for 64-bit integers */
       return n ;
  }

#include <iostream>using namespace std;int BitCount1(unsigned int n )
{int nCount = 0;while(n){//nCount+= n &0x1u;//n >>= 1;if( n & 0x1 )nCount++;n = n>>1;}return nCount;
}int BitCount2( unsigned int n )
{int nCount = 0;while(n){nCount++;n &= (n-1);}return nCount;
}int BitCount3( unsigned int n )
{int nCount = 8 * sizeof(int);n ^= (unsigned int)-1;while(n){nCount--;n &=(n-1);}return nCount;
}int main()
{cout<<"Count1:"<<BitCount1(0x5)<<endl;cout<<"Count2:"<<BitCount2(4)<<endl;cout<<"Count3:"<<BitCount3(7)<<endl;int a = 0x100;cout<<"0x100:"<<a<<endl;cout<<"0xFF:"<<0xFF<<endl;cout<<"int-1:"<<(unsigned int)-1<<endl;cout<<"sizeof(unsigned int):"<<sizeof(unsigned int)<<endl;cout<<"sizeof(short int):"<<sizeof(short)<<endl;return 0;
}


这篇关于计算一个无符整数中1Bit的个数(1)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1033105。

相关文章

spoj705( 求不相同的子串个数)

spoj705( 求不相同的子串个数)

题意：求串s的不同子串的个数 解题思路：任何子串都是某个后缀的前缀，对n个后缀排序，求某个后缀的前缀的个数，减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin
阅读更多...
PTA求一批整数中出现最多的个位数字

PTA求一批整数中出现最多的个位数字

作者 徐镜春 单位 浙江大学 给定一批整数，分析每个整数的每一位数字，求出现次数最多的个位数字。例如给定3个整数1234、2345、3456，其中出现最多次数的数字是3和4，均出现了3次。 输入格式： 输入在第1行中给出正整数N（≤1000），在第二行中给出N个不超过整型范围的非负整数，数字间以空格分隔。 输出格式： 在一行中按格式“M: n1 n2 ...”输出，其中M是最大次数，n
阅读更多...
poj 1113 凸包+简单几何计算

poj 1113 凸包+简单几何计算

题意： 给N个平面上的点，现在要在离点外L米处建城墙，使得城墙把所有点都包含进去且城墙的长度最短。 解析： 韬哥出的某次训练赛上A出的第一道计算几何，算是大水题吧。 用convexhull算法把凸包求出来，然后加加减减就A了。 计算见下图： 好久没玩画图了啊好开心。 代码： #include <iostream>#include <cstdio>#inclu
阅读更多...
uva 1342 欧拉定理（计算几何模板）

uva 1342 欧拉定理（计算几何模板）

题意： 给几个点，把这几个点用直线连起来，求这些直线把平面分成了几个。 解析： 欧拉定理： 顶点数 + 面数 - 边数= 2。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc
阅读更多...
uva 11178 计算集合模板题

uva 11178 计算集合模板题

题意： 求三角形行三个角三等分点射线交出的内三角形坐标。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <
阅读更多...
XTU 1237 计算几何

XTU 1237 计算几何

题面： Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa
阅读更多...
XTU 1233 n个硬币连续m个正面个数（dp）

XTU 1233 n个硬币连续m个正面个数（dp）

题面： Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o
阅读更多...
整数Hash散列总结

整数Hash散列总结

方法：    step1  :线性探测  step2 散列   当 h(k)位置已经存储有元素的时候，依次探查(h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中，S为 数组长度。 HDU 1496   a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数  const int MaxN = 3000
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
计算数组的斜率，偏移，R2

计算数组的斜率，偏移，R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2