找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 410|回复: 0
收起左侧

[基础刷题题目讨论] 统计二进制表示‘1‘的个数

[复制链接]

1

主题

0

精华

9

积分

新米人

Rank: 1

积分
9
发表于 6-24-2018 12:03 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
基础知识

在计算机中, 数字是以二进制储存的.
我们平常生活中用的是十进制.
假设对于十进制 10030, 我们想得到第二位的数字是多少的话需要这样:

  • (10030 / 10^1 ) % 10


也就是需要先把需要查询的数字移到个位, 然后在取模即可.

而对于二进制 10010, 想得到第二位的数字就有很多方法了.

  • (10010 >> 1 ) & 1
  • (10010 & 10) >> 1


其中上面的第一个方法和十进制的思想相同, 第二个是想把其他位置0, 然后把第二位移到个位.

然后我们就可以判断这位是不是我们想要的数字了。

  • if((10010 >> 1 ) & 1 == 1){
  •     //do some thing
  • }


然后对于二进制,每一位只有0或1,所以当那一位是1时,和1判断是否相等得到true, 而数字1依然是true
于是我们可以简写为下面的形式

  • if((10010 >> 1) & 1){
  •     //do some thing
  • }


而现在我们要做的是统计一个32位整数的二进制有多少个1.

最简单的算法

实际上最简单的方法是下面的代码, 直接一位一位的判断即可.

  • unsigned __countbits(unsigned x){
  •     unsigned n=0;
  •     for(int i=0;i<32;i++){
  •         n += x&1;
  •         x>>=1;
  •     }
  •     return n;
  • }


相对暴力的算法

大家可以看到, 当 x 为0 的时候, 我们并没有判断还有没有1, 而是继续循环, 直到32位遍历结束.
什么意思呢, 假设传入的是 1, 我们进入循环之后, x就变成0了, 然后再循环是不会更新答案n的, 所以我们可以结束循环了.

于是下面的代码就出来了.
其中 使用了逗号表达式, ture 与 false 只与最后一个表达式有关系.

  • unsigned __countbits(unsigned x){
  •     unsigned n=0;
  •     while(n +=(x&1) , x >>= 1);
  •     return n;
  • }


与 1 的个数有关的算法

大家先来看一个实验.
假设我们有 二进制 101100, 这个二进制减一后是 101100 - 1 = 101011, 这两个数字的后三位不同, 且数字相反.
然后这两个数字进行与操作后得到 101100 & 101011 = 101000, 我们可以发现少了一个 1.
然后再来一次, 原始数字: 101000, 减一: 101000 - 1 = 100111, 与操作 : 101000 & 100111 = 100000,
最后再来一次, 原始数字: 100000, 减一: 100000 - 1 = 011111, 与操作 : 100000 & 011111 = 0.

我们发现1的个数与我们进行的那个运算次数相等.
那这是不是运气呢?
假设这个数字的二进制有1, 则我们找到最后一个1, 1后面可能若干个0. 这个数字减1时, 前面若干0那些位都不够减的, 需要向高位借1, 直到最后一个1, 借到了1, 于是1变成0.
后面的位向高位借到1时是2, 再借给低位一个, 又变成了1.
最后一位借到1是2, 减去我们需要减的1也变成1了.
原来这个不是运气, 也不是偶然, 所有数字都遵循这个规律的.
于是我们可以使用这个规律来计算1的个数了.

复杂度就是1的个数了.
需要注意的是对于0, 是没有1的, 我们需要特判, 不然会出错的, 我就踩过这个.

  • unsigned _countbits(unsigned x){
  •     unsigned n=0;
  •     while(x && (++n , x&=x-1));
  •     return n;
  • }


log 算法 分支法

用过二分查找的人应该很喜欢二分吧, 复杂度那是 log 级的, 用着太爽了.
而我们32位整数, log(32) = 5, 也就是我们只需要5步就可以得到我们想要的答案了.

但是怎么二分了.
首先将32位数看成相互独立的32个 0-1 数字.
然后两两相加, 这样我们就有16个数字了.
然后再两两相加, 就变成8个数字了, 接着再两两相加变成4个, 然后两个, 最后一个数字.
由于是32位数字的和, 所以答案刚好就是1的个数啦.

现在问题是怎么数字两两相加呢?
32位太多了, 我们看看4位的数字吧, 假设是 1101.
要想相邻两位相加, 那就需要右移一下, 这样就能对齐了.
于是我们得到下面的数据.

  • 11 01
  • 01 10


然后我们发现这个时候还不能相加, 因为对于两位数字来说, 高位还有垃圾数据, 我们需要清理掉.
需要清理的数据刚好都是高位, 那就把那些高位的位置置为0吧.

  • 11 01 & 01 01 = 01 01
  • 01 10 & 01 01 = 01 00


然后这个时候就可以相加了.

  • 01 01 + 01 00 = 10 01


这两个数字接下来怎么相加呢?
应该是右移两位了.

  • 1001
  • 0010


发现高位还有垃圾数据, 需要清理掉.

  • 1001 & 0011 = 0001
  • 0010 & 0011 = 0010


然后相加

  • 0001 + 0010 = 0011


0011 的十进制就是3, 这样果然可以得到二进制1的个数.

而且可以总结为

  • 右移 1位. 与数字: 0101 => 0x5
  • 右移 2位. 与数字: 0011 => 0x3


那对于32位整数需要操作哪五部呢?

  • 右移 1位. 与数字: 01010101010101010101010101010101 => 0x55555555
  • 右移 2位. 与数字: 00110011001100110011001100110011 => 0x33333333
  • 右移 4位. 与数字: 00001111000011110000111100001111 => 0x0F0F0F0F
  • 右移 8位. 与数字: 00000000111111110000000011111111 => 0x00FF00FF
  • 右移16位. 与数字: 00000000000000001111111111111111 => 0x0000FFFF


由上面的方法, 我们可以快速的写出32位对应的代码了.

  • uint countbits(uint x) {
  •     uint mask[]= {0x55555555,0x33333333, 0x0F0F0F0F,
  •                   0x00FF00FF, 0x0000FFFF
  •                  };
  •     for(uint i=0,j=1; i<5; i++,j<<=1) {
  •         x=(x & mask[i]) + ((x>>j) & mask[i]);
  •     }
  •     return x;
  • }


打表法

分治法虽然是 log 级的, 但是有时候还是感觉复杂度太高, 想追求O(1)的做法.
这个时候就需要拿出空间来换取时间了.
什么意思呢?
我们想求x的二进制1的个数, 如果我们已经事先求出来了的话, 那是不是只需要取得那个值不就行了.
但是32位整数太多了, 我们存不下.
那16位就很小了, 就几万, 可以试试.

  • const int OneNumMax = 1<<16;
  • int oneNum[OneNumMax];
  • int init(){
  •     for(int i = 1; i < OneNumMax; ++i) {
  •         oneNum[i = oneNum[i >> 1 + (i & 1);
  •     }
  •     return 0;
  • }


那么对于32位整数, 不就是两个16位整数吗?

对于高16位数字, 我们直接右移16位就得到了.
对于低16位, 我们可以进行与运算把高位置0得到.
于是代码就可以敲出来了.

  • unsigned countbits(unsigned x) {
  •     return oneNum[x >> 16 + oneNum[x & ((1 << 16) - 1)];
  • }


MIT HACKMEM

这个算法是 MIT 实验室的备忘录中的一个算法.
上面我们看到了二分的好处, 按我们如果三分会怎么样呢?

三分的第一步是得到每三位的数字和.

于是有人这样想了

  • master = 011111111111;
  • x = (x & master) + ((x >> 1) & master) + ((n >> 2) & master);


那有没有其他方法呢?

对于三位, 我们的目的是下面的映射

  • 000 => 0
  • 001 => 1
  • 010 => 1
  • 011 => 2
  • 100 => 1
  • 101 => 2
  • 110 => 2
  • 111 => 3


然后我们发现一个奇妙的等价公式

  • 321         321   32   3
  • 000 => 0 <= 000 - 00 - 0
  • 001 => 1 <= 001 - 00 - 0
  • 010 => 1 <= 010 - 00 - 1
  • 011 => 2 <= 011 - 01 - 0
  • 100 => 1 <= 100 - 10 - 1
  • 101 => 2 <= 101 - 10 - 1
  • 110 => 2 <= 110 - 11 - 1
  • 111 => 3 <= 111 - 11 - 1


竟然这个巧, 于是下面的式子也是成立的.

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


现在我们得到了每三位的数字和, 然后你会不会想我是该计算每六位的数字和了?
恭喜你, 打对了.
32位共有10个三位和一个两位.

每个三位最高值为 11, 相加是 110, 所以低3位就可以表示了, 高三位是没有用的, 因此可以计算结束后在置0.

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


这个时候, 我们得到的是每六位的数字和了.
共有5个六位和一个两位.
其中5个六位的数字都在低三位, 高三位确定为0.
数字可以表示为

  • tmp = a*64^5 + b*64^4 + c*64^3 + d*64^2 + e*64^1 + f


我们的目标是求 a+b+c+d+e+f 的答案. 然后又有人发现一个公式.
前面的数字都是64的幂数倍, 对于这个规律, 可以使用模 64-1 来抵消的.

  •   64^k % 63
  • = (64 % 63)^k % 63
  • = 1


所以

  • a * 64^k % 63 = a


也就是说

  •   tmp % 63
  • = (a*64^5 + b*64^4 + c*64^3 + d*64^2 + e*64^1 + f) % 63
  • = ((a*64^5 % 63) + (b*64^4 % 63) + (c*64^3 % 63) + (d*64^2 % 63) + (e*64^1 % 63) + (f % 63)) % 63
  • = (a % 63 + b%63 + c%63 + d%63 + e%63 + f%63) % 65
  • = (a + b + c + d + e + f) % 63


而我们32位的答案刚好最多是32, 所以可以模上63, 因此下面的公式就诞生了.

  •   tmp % 63
  • = a + b + c + d + e + f


于是我们的二进制中1的个数也可以用这个方法做了.

  • ans = tmp % 63


代码综合起来就是

  • int bitCount ( unsigned n ) {
  •     unsigned tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
  •     return ( (tmp + (tmp >> 3) ) & 030707070707) % 63;
  • }


注:最后一个算法时我在看 sphinx 源代码的时候看到的.

64位中二进制1的个数

有位同学读了我的记录,然后很热情的反馈了很多问题。
最后他说他想要的其实是一个计算64位数字二进制1的个数,于是我便附加了一个小节。

windows 一个坑

在开始之前我们定义一些类型吧。
按照 acm 的习惯,我喜欢把 long long 定义为 LL 。

为什么呢? 这个你就该去查查 windows 的手册了,虽然现在 windows 也慢慢的开源了,但是它在程序员心中的丑陋印象还是很难改变的。

简单的说就是在 windows 下, 你使用 long long 的话, 需要使用 __int64 代替,否则肯定会出错。
至于为什么,那是因为在 windows 下根本就没有 long long 这个关键字。
大家可以看看windows下的C++ Keywords
当然,这个是 Microsoft C++ 编译器下的关键字,有人会说我安装的是 GNU 的 c++ 编译器。
虽然 windows 在官网文档上一直强调 long long 与 __int64 等价,但是事实上并不等价的。
好了,不说废话了,我的所有程序都会加上下面这个宏的。

  • #ifdef __int64
  •     typedef __int64 LL;
  •     typedef  unsigned __int64  ULL;
  • #else
  •     typedef long long LL;
  •     typedef unsigned long long ULL;
  • #endif


暴力求64位1的个数

暴力程序虽然暴力,但是有时候是最可靠的程序。
比如用来验证我们的其他程序是否正确。

  • int _countbits(ULL x) {
  •     int n=0;
  •     while(n +=(x&1) , x >>= 1);
  •     return n;
  • }


与1的个数有关复杂度

这个程序完全可以代替上面的暴力程序,而且只是还快点。

  • int _countbits(ULL x) {
  •     int n=0;
  •     while(x && (++n , x&=x-1));
  •     return n;
  • }


打表法

这个打表的复杂度看起来就稍微多了一些。

  • const int OneNumMax = 1<<16;
  • ULL oneNum[OneNumMax];
  • int init() {
  •     for(int i = 1; i < OneNumMax; ++i) {
  •         oneNum[i = oneNum[i >> 1 + (i & 1);
  •     }
  •     return 0;
  • }
  • int countbits(ULL x) {
  •     static int a = init();
  •     static  ULL mask = (1ULL << 16) - 1;
  •     ULL ans = 0;
  •     for(int i=0;i<4;i++,x>>=16){
  •         ans += oneNum[x & mask];
  •     }
  •     return ans;
  • }


错误的MIT HACKMEM

关于测试代码可以参考

  • ULL mitHeakArray[3];
  • bool okMitHeak = false;
  • int initMitHeakArray() {
  •     if(okMitHeak) {
  •         return true;
  •     }
  •     ULL a = 011ULL, b = 033ULL, c = 07ULL;
  •     for(int i=0; i<11; i++) {
  •         a = (a << 6) | 011ULL;
  •         b = (b << 6) | 033ULL;
  •         c = (c << 6) | 07ULL;
  •     }
  •     mitHeakArray[0 = a;
  •     mitHeakArray[1 = b;
  •     mitHeakArray[2 = c;
  •     okMitHeak = true;
  •     return 0;
  • }
  • int bitCount ( ULL n ) {
  •     static int a = initMitHeakArray();
  •     ULL tmp = n - ((n >> 1) & mitHeakArray[1]) - ((n >> 2) & mitHeakArray[0]);
  •     return ( (tmp + (tmp >> 3) ) & mitHeakArray[2]) % 63;
  • }



写完上面的代码, 有人提醒我有问题哦。
64位的整数模63怎么可能得到答案呢?
此时我大呼:呀,只顾着套算法模板,把这个遗漏了。

什么情况呢?

应该还记得这段话吧

而我们32位的答案刚好最多是32, 所以可以模上63, 因此下面的公式就诞生了.

从而我们得到下面的公式

  • tmp % 63 = a + b + c + d + e + f


但是我们这里是 64位整数,答案最多是64位。
这怎么可以模上 63 呢?

这个时候有两个选择:

  • 找个更宽的位数,比如7位或八位。
  • 对63位和64位特殊判断。

现在我们分别来看看吧。

特殊判断 MIT HACKMEM

怎么特殊判断呢?
当 n 的答案是64时,就是全1了。
所以这个好判断,直接判断 ~n 是不是 0 啦。

比如下面的代码

  • if(~n == 0){
  •     return 64;
  • }


那对于63个1的情况,会怎么样呢?
首先没有进位,只是 答案应该是 63, 而我们模上 63, 得到一个答案0了。
所以我们判断这个数字到底是不是0就可以了。

  • if(ans == 0 && n != 0){
  •     ans = 63;
  • }


这样我们就可以得到答案了。
完整代码如下:

  • int bitCount ( ULL n ) {
  •     if(~n == 0){
  •         return 64;
  •     }
  •     static int a = initMitHeakArray();
  •     ULL tmp = n - ((n >> 1) & mitHeakArray[1]) - ((n >> 2) & mitHeakArray[0]);
  •     int ans = ( (tmp + (tmp >> 3) ) & mitHeakArray[2]) % 63;
  •     if(ans == 0 && n != 0){
  •         ans = 63;
  •     }
  •     return ans;
  • }


加宽的 MIT HACKMEM

64位,至少需要7位。
我们为了方便分治,只好采用8位了。

8位不刚好是二分的节奏嘛。
于是我们可以把二分的代码搬过来。

我们要做的是什么呢?
将64二进制数据按每八个一组,这8位并储存这八位1的个数。
做到这个很简单的,只需要第一次计算二位的,然后四位的,最后8位的即可。

  • for(uint i=0,j=1; i<3; i++,j<<=1) {
  •     x=(x & mitHeakMask[i]) + ((x>>j) & mitHeakMask[i]);
  • }


这样进行三次就得到每8位的1的个数了。

然后我们可以得到这个公式

  • x = a*256^8 + b*256^7 + c*256^6 + d*256^5 + e*256^4 + f*256^3 + g*256^2 + h*256^1 + i*256;


我们需要得到的是 a + b + c + d + e + f + g + h + i  的和。
这个和远远小于 255, 于是我们可以取模 255 了。

  •   x % 255
  • = (a*256^8 + b*256^7 + c*256^6 + d*256^5 + e*256^4 + f*256^3 + g*256^2 + h*256^1 + i*256) % 255
  • = ((a*256^8)  % 255 + (b*256^7)  % 255 + (c*256^6)  % 255 + (d*256^5)  % 255 + (e*256^4)  % 255 + (f*256^3)  % 255 + (g*256^2)  % 255 + (h*256^1)  % 255 + i*256) % 255
  • = (a + b + c + d + e + f + g + h + i) % 255
  • = a + b + c + d + e + f + g + h + i


所以答案就是 ans = x % 255

完整代码如下:

关于测试代码可以参考这里

  • ULL mitHeakMask[3];
  • bool okMitHeak = false;
  • int initMitHeakMask() {
  •     if(okMitHeak) {
  •         return true;
  •     }
  •     ULL a = 0x55ULL, b = 0x33ULL, c = 0x0FULL;
  •     for(int i=0; i<8; i++) {
  •         a = (a << 8) | 0x55ULL;
  •         b = (b << 8) | 0x33ULL;
  •         c = (c << 8) | 0x0FULL;
  •     }
  •     mitHeakMask[0 = a;
  •     mitHeakMask[1 = b;
  •     mitHeakMask[2 = c;
  •     okMitHeak = true;
  •     return 0;
  • }
  • uint countbits(ULL x) {
  •     int a = initMitHeakMask();
  •     for(uint i=0,j=1; i<3; i++,j<<=1) {
  •         x=(x & mitHeakMask[i]) + ((x>>j) & mitHeakMask[i]);
  •     }
  •     return ans%255;
  • }



您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表