如何在大规模字节序列中快速统计1的个数

开篇

本题来源于《编程珠玑》第9章【代码调优】课后习题7，旨在实现在一个大规模的字节序列中，高效统计1的个数。

题目描述

给定一个非常长的字节序列（假设有十亿或万亿），如何高效的统计1的个数呢？（也就是说，在整个序列中有多少个位的值为1？）

思路分析

在一个超长的字节序列中快速统计1的个数，可以利用查表法。
因为一个1个字节为8位，也就是字节共计有2的8次方，也就是256种可能。所以提前建立一个表来统计这256种可能中包含1的个数。
在统计字节序列中1的个数时，直接查表，从而获取1的个数。

代码实现

#include <stdio.h>
#include <stdint.h> // 为了用uint8_t

// 创建一个包含0到255的字节值的表，每个表项存储该字节中1的个数
// 这里之所以创建0到244的字节值的表，是因为一个字节有8位，也就是2的8次方种可能
// 例如:00000000包含0个1，而11111111包含8个1
void create_bit_cnt_table(int bit_cnt_table[256]) {
for (int i = 0; i < 256; i++) {
int count = 0;
int num = i;
while (num) {
count += num & 1;//如果最低位是1，计数+1
num >>= 1; // 右移1位
}
bit_cnt_table[i] = count;
}
}

// 统计给定字节序列中1的位数
unsigned long long count_ones_in_byte_seq(uint8_t* byte_seq, size_t length) {
int bit_cnt_table[256];
create_bit_cnt_table(bit_cnt_table); //创建查表

unsigned long long total_ones = 0;

for (size_t i = 0; i < length; i++) {
total_ones += bit_cnt_table[byte_seq[i]]; // 通过查表统计每个字节中1的个数
}

return total_ones;
}

int main() {
// 模拟一个字节序列
uint8_t byte_seq[] = { 0xFF, 0x0F,0xF0,0x00,0x01 };
rsize_t length = sizeof(byte_seq) / sizeof(byte_seq[0]);

printf("length: %zu\n", length);

// 调用函数统计1的位数
unsigned long long res = count_ones_in_byte_seq(byte_seq, length);

printf("1的个数为: %llu\n", res);

return 0;
}

代码截图

运行效果

注

以上便是本篇文章的全部内容，希望对您有所帮助。
感谢阅读。

原文地址：https://blog.csdn.net/qq_26854355/article/details/142727874

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！