c++ - 连续内存块中的位计数

Question

我在一次采访中被问到以下问题。

int countSetBits(void *ptr, int start, int end); 

简介: 假设 ptr 指向一大块内存。将此内存视为连续的位序列，start 和 end 是位位置。假设 start 和 end 具有正确的值，并且 ptr 指向已初始化的内存块。

问题: 编写一个 C 代码来计算从 start 到 end [包括] 设置的位数并返回计数。

只是为了更清楚

 ptr---->+-------------------------------+
         | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
         +-------------------------------+
         | 8 | 9 |                   |15 |
         +-------------------------------+
         |                               |
         +-------------------------------+
              ...
              ...
         +-------------------------------+
         |               | S |           |
         +-------------------------------+
              ...
              ...
         +-------------------------------+
         |    | E |                      |
         +-------------------------------+
              ...
              ...

我的解决方案:

int countSetBits(void *ptr, int start, int end )
{
    int count = 0, idx; 

    char *ch; 

    for (idx = start; idx <= end; idx++) 
    {     ch = ptr + (idx/8); 

          if((128 >> (idx%8)) & (*ch)) 
          {
                   count++; 
          }
    }

    return count; 
}

我在面试中给出了一个非常冗长且效率低下的代码。我后来研究它并提出了上述解决方案。

我很确定 SO 社区可以提供更优雅的解决方案。我只是好奇地想看看他们的 react 。

PS:以上代码未编译。它更像是一个伪代码，可能包含错误。

Answer 1

在我看来，最快速有效的方法是使用包含 256 个条目的表，其中每个元素代表索引中的位数。索引是内存位置的下一个字节。

类似这样的:

int bit_table[256] = {0, 1, 1, 2, 1, ...};
char* p = ptr + start;
int count = 0;
for (p; p != ptr + end; p++)
    count += bit_table[*(unsigned char*)p];