如何快速计数位在一系列整数呢？ [英] How to quickly count bits in a series of ints?

问题描述

更新：请阅读code，它是不是在一个INT计数位

是否有可能提高以下code性能与一些聪明的汇编程序？

Is it possible to improve performance of the following code with some clever assembler?

uint bit_counter[64];

void Count(uint64 bits) {
  bit_counter[0] += (bits >> 0) & 1;
  bit_counter[1] += (bits >> 1) & 1;
  // ..
  bit_counter[63] += (bits >> 63) & 1;
}

Count函数是在我的算法中最内层循环。

Count function is in the most inner loop of my algorithm.

更新： 建筑：86，Sandy Bridge的，所以SSE5，AVX及以上技术都可以使用。 位变量几乎是随机位（接近零的一半，另一半的人）

Update: Architecture: x86, Sandy Bridge, so SSE5, AVX and older tech can be used. "bits" variable has almost random bits (close to half zeros and half ones)

推荐答案

也许你可以做8一次，采取8位间隔8开，并保持8 UINT64的对数。这是每一个计数器只有1个字节，因此你只能积累255调用的计数之前，你必须解开这些UINT64的。

Maybe you can do 8 at once, by taking 8 bits spaced 8 apart and keeping 8 uint64's for the counts. That's only 1 byte per single counter though, so you can only accumulate 255 invocations of count before you'd have to unpack those uint64's.

这篇关于如何快速计数位在一系列整数呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！