MIT HAKMEM算法-BitCount算法

MIT HAKMEM算法

1.问题来源

牛客刷题

• 问题描述:

#include <iostream>
using namespace std;

unsigned int fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return f(n-1)+f(n-2);
}

void count(int n)
{
    unsigned int temp= n - ((n>>1)&033333333333) - ((n>>2)&011111111111)
    std::cout<< ((temp+(temp>>3))&030707070707) %63 <<std::endl;
}

int main()
{
    count(f(7));
    count(f(9));
    return 0;
}

哈哈，看见这个题
这不是 fib数列递归运算后再进行二进制的运算

摊手、哈哈 菜 计算不出来！
查找资料 - 这个count函数就是统计bit个数的
f(7)=21=00010101B
f(9)=55= 00110111B

输出: 3,5

2.问题描述:

现在来研究研究这个count函数-统计整数(二进制)中“1”的个数

一些知识点

• 1.整数性的数值
  \(i=a_{0} * 2^{0} + a_{1} * 2^{1}+a_{2}*2^{2}+...+a_{n}* 2^{n}\)
  所以count “1”的个数
  \(count=a_{0}+a_{1}+a_{2}+...+a_{n}\)

• 2.对于任何自然数n的N次幂 \(n^{N}\),用n-1 取模得数为1
  \[ n^{N} \%(n-1)=1 \]
  利用归纳法来证明:
  假设 \(n^{k-1} \%(n-1)=1\) 成立
  证明 \(n^{k} \%(n-1)=1\)
  \[n^{k} = (n-1)*n^{k-1} + n^{k-1} \]
  \[ (n-1)*n^{k-1} \%(n-1)+ n^{k-1} \%(n-1)=0+1=1\]

• 3.一个系数 为\(a_{i}\)以n为底的多项式P(N)
  \[P(N)\%(n-1)=\sum a_{i} \%(n-1)\]
  保证$\sum a_{i} $小于余数 $\sum a_{i} < n-1 $
  可以推导出
  \[P(N)\%(n-1)=\sum a_{i}\]
  32bit的整数，可以取 n=64 n-1=63作为余数来实现count

• 4.将32位二进制数的每6位作为一个单位，看作以64为底的多项式
  \(I=t_{0}* 64^{0}+ t_{1} * 64^{1} +...+t_{n} * 64^{n}\)
  各个单位中的6位数变为这6位中含有的'1'的个数，再用63取模，就可以得到所求的总的'1'的个数。

• 5.其中任意一项的6位数ti进行考虑，最简单的方法显然是对每次对1位进行mask然后相加
  (ti>>5)&(000001) + (ti&>>4)(000001) + (ti>>3)&(000001) + (ti>>2)&(000001) + (ti>>1)&(000001) + ti&(000001)

初步实现代码

int bitcount(unsigned int n)
{
    unsigned int tmp;

    tmp = (n &010101010101)
     +((n>>1)&010101010101)
     +((n>>2)&010101010101)
     +((n>>3)&010101010101)
     +((n>>4)&010101010101)
     +((n>>5)&010101010101);

    return (tmp%63);
}

• 6.位数中最多只有6个'1'，也就是000110，只需要3位有效位。上面的式子实际上是以1位为单位提取出'1'的个数再相加求和求出6位中'1'的总个数的，所以用的是&(000001)。如果以3位为单位算出'1'的个数再进行相加的话，那么就完全可以先加后MASK。
  tmp = (ti>>2)&(001001) + (ti>>1)&(001001) + ti&(001001)
  (tmp + tmp>>3)&(000111)

int bitcount(unsigned int n)
{
    unsigned int tmp;

    tmp = (n &011111111111)
     +((n>>1)&011111111111)
     +((n>>2)&011111111111);
     
    tmp = (tmp + (tmp>>3)) &030707070707;

    return (tmp%63);
}

• 7.最终的优化代码

    unsigned int tmp;

    tmp = n
        - ((n >> 1) & 033333333333)
        - ((n >> 2) & 011111111111);

    tmp = (tmp + (tmp >> 3)) & 030707070707

    return (tmp%63);
}

参考链接