Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
132 lines (96 sloc) 3.87 KB
layout title date categories
post
64位整数中有多少个1
2018-09-04 09:00:05 +0800
算法

In short

这是一个看似简单的问题,学过编程的同学不难解决这个问题,但怎么样更优雅地解决问题是这篇文章想讲述的。

Main

C 语言在不同平台上数据长度有所差异,我测试机器是 64 位:

printf("%lu %lu %lu\n", sizeof(unsigned int), sizeof(unsigned long), sizeof(unsigned long long));
// output: 4 8 8

理解 C 语言中的类型转换机制能够帮助理解下面代码。

C 语言中的强制类型转换,比如 unsigned int 与 int 之间的转换,采用二进制不变方式,也就是改变解析的方式,对于编译器来说就是拷贝一块内快。比如:

int x = -1; // 位模式:11111111 11111111 11111111 11111111
unsigned int y = (unsigned int)x; // 位模式:11111111 11111111 11111111 11111111,也就是 y == 2 ^ 32 - 1 == 4294967295
printf("%u", y);
// output: 4294967295

如果将 64-bit int 转化为 32-bit,采取低位截断方式。比如:

unsigned long long y = 0xffffffffffffffff;
int x = y; // 位模式:11111111 11111111 11111111 11111111
printf("%d\n", x);
// output: -1

暴力破解

思路:遍历 64 位就知道 64-bit 整数有多少个 1。

unsigned int counter(unsigned long long n)
{
    unsigned int cnt = 0;
    while (n)
    {
        if (n & 1) cnt += 1;
        n >>= 1;  
    }
    return cnt;
}

在一般应用场景下,这个解决方案已经能够满足了,最多循环次数为 64。

借助数学

数学是伟大的学科,这个问题也可以借助数学进行优化。

数学规律:对于任意一个非 0 整数 n,n & (n - 1) 能够去除 n 二进制中最低位的 1。

如 4-bit 整数 n == 5,二进制表示为 0101,n-1 == 4,二进制表示为 0100,0101 & 0100 == 0100

借助这个规律有以下代码实现:

unsigned int counter(unsigned long long n)
{
    unsigned int cnt = 0;
    while (n)
    {
        cnt += 1;
        // 去除最低位的 1
        n &= n - 1;
    }
    return cnt;
}

一个 64-bit 整数 1 的平均个数为 32,所以平均循环次数为 32。

查表法

可以先将所有 8-bit 整数,-128 ~ 127 预先计算一遍对应有多少个 1,下次计算时就可以直接查表。

static unsigned int table[255];

void init()
{
    for (unsigned int i = 0; i <= 0xff; ++i)
    {
        table[i] = table[i & (i - 1)] + 1;
    }
}

unsigned int counter(unsigned long long n)
{
    unsigned int cnt = 0;
    while (n)
    {
        cnt += table[(n & 0xff)];
        n >>= 8;
    }
    return cnt;
}

如果采用 8-bit 作为切分需要查 8 次表,那么如果内存允许情况下,按照 32-bit 切分只需要查 2 次表是否会更快呢?

如果单纯站在算法的角度思考问题,答案是肯定的。但是如果需要考虑到计算机运行环境,答案是否定的。

为什么,按照 8-bit 切分需要的内存为 (2 ^ 8)B == 256B 按照 32-bit 切分需要的内存为 (2 ^ 32)B == 4GB

而普通 CPU 缓存大概为 10MB左右,Unix 系操作系统可通过 cat /proc/cpuinfo 查看当前电脑 CPU 信息,我电脑单核 CPU 的缓存:

cache size	: 6144 KB

也就是说按照 8-bit 切分的数据能够完全存放于 CPU 告诉缓存中,高速缓存的速度是最接近 CPU 运算速度的存储介质,而按照 32-bit 切分的数据只能够存放于内存,每次查表还需要重新将数据从内存加载到高速缓存中,而且假设 4GB 数据被访问的可能性相等,那么也就是一个被加载进高速缓存的数据只用于一次查询后就失效了。

总而言之,按 8-bit 切分无论是时间还是空间上都是更好的方案。

Conclusion

无论多么简单的问题都会很大的优化空间,除了算法,还要从计算机系统角度思考问题。