快速算法，以计数的数字1为二进制数

Question

1. 如果我有二进制数0111000111111，有什么快速算法可以计算1的数量吗？

2. 如果0111000111111是字符串(例如"011100011111"(有什么快速算法可以计算字符串中1的数量吗？

Answer 1

一种相对快速的方法是预计算所有字节值的位计数表，并对(无符号(整数的四个字节求和。

byte NB[256]= { 0, 1, 1, 2, 1, 2, 2, 3, 1, 1, ... };
N= NB[U & 255] + NB[(U >> 8) & 255] + NB[(U >> 16) & 255] + NB[(U >> 24) & 255];

您可以针对每个切片的不同位数进行调整。