C中的位翻转-计数位 [英] Bit Twiddling in C - Counting Bits

问题描述

我要计算一个非常大的位向量(即100,000个位)中设置的位.

I want to count the bits that are set in an extremely large bit-vector (i.e. 100,000 bits).

我当前正在做的是使用指向char的指针(即char * cPtr)指向位数组的开头.然后，我:

What I am currently doing is using a pointer to char (i.e. char *cPtr) to point to the beginning of the array of bits. I then:

1. look at each element of the array (i.e. cPtr[x]),   
2. convert it to an integer (i.e. (int) cPtr[x])   
3. use a 256 element look-up table to see how many bits are set in the given byte (i.e. cPtr[x]). 

在我看来，如果我改用短int指针(即short int * sPtr)，那么我将只需要一半的查找，但是需要一个65534元素的查找表，该表将具有内存使用方面的成本.

It occurs to me that if I use a short int pointer instead (i.e. short int * sPtr), then I will only need half as many look-ups, but with a 65534 element look-up table, which will have its own cost in memory usage.

我想知道每次检查的最佳位数是多少.另外，如果该数字不是某个预设类型的大小，我该如何向下移动我的位向量，并将指针设置为在位数组的起始位置之后任意数量的 ANY 位.

I'm wondering what is the optimal number of bits to examine each time. Also, if that number is not the size of some preset type, how can I walk down my bit-vector and set a pointer to be ANY arbitrary number of bits past the starting location of the bit array.

我知道还有其他计数位数的方法，但是现在我想确定可以在与其他方法进行比较之前优化此方法.

I know there are other ways to count bits, but for now I want to be certain I can optimize this method before making comparisons to other methods.

推荐答案

我想知道每次检查的最佳位数是多少

I'm wondering what is the optimal number of bits to examine each time

找出答案的唯一方法是测试.请参阅此问题，以获取有关一次计数32位最快方法的讨论.

The only way to find out is to test. See this question for a discussion of the fastest way to count 32 bits at a time.

此外，如果该数字不是某些预设类型的大小，我该怎么办 走下我的位向量并将指针设置为任何任意数字 超过位数组起始位置的位.

Also, if that number is not the size of some preset type, how can I walk down my bit-vector and set a pointer to be ANY arbitrary number of bits past the starting location of the bit array.

您不能将指针设置为任意位.大多数机器都有字节寻址，有些只能寻址字.

You can't set a pointer to an arbitrary bit. Most machines have byte-addressing, some can only address words.

您可以构造一个以任意位开头的单词，如下所示:

You can construct a word starting with an arbitrary bit like so:

long wordAtBit(int32_t* array, size_t bit)
{
    size_t idx = bit>>5;
    long word = array[idx] >> (bit&31);
    return word | (array[idx+1] << (32 - (bit&31));
}

这篇关于C中的位翻转-计数位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！