2

我正在逐字节运行二进制数据的内存块。

目前我正在做这样的事情：

for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    ((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
    ((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
    ((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
    ((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
    ((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
    ((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
    ((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
    ((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}

面具在哪里：

for (i = 0; i < 8; i++)
{
    Masks[i] = 1 << i;
}

（不知何故，我没有设法在循环或内联函数中做到这一点，所以我把它写出来了。）

有人对如何改进第一个循环有任何建议吗？我对深入浅出相当缺乏经验。

这似乎是一件愚蠢的事情。但我正在实施压缩算法。我只想让位访问部分正确。

谢谢！

PS：这是在 Visual Studio 2008 编译器上。因此，如果建议适用于该编译器，那就太好了。

PPS：我刚刚意识到，我不需要增加两个计数。一个就足够了。然后计算最后的总位数的差异。但这将特定于仅计数。我真正想要快速完成的是位提取。

编辑：提出的查找表想法很好。我意识到我在标题中提出了错误的问题。因为最后我想做的不是计算位，而是尽可能快地访问每个位。

另一个编辑：是否可以在数据中仅将指针推进一位？

另一个编辑：感谢您迄今为止的所有回答。

我想在接下来的步骤中实现的是一个不分析上下文的简单二进制算术编码器。所以我现在只对单个位感兴趣。最终它将成为一个上下文自适应的 BAC，但我将把它留到以后。

处理 4 个字节而不是 1 个字节可能是一种选择。但是超过 32 位的循环也很昂贵，不是吗？

4

11 回答 11

16

最快的方法可能是建立一个字节值与该字节中设置的位数的查找表。至少这是我在谷歌面试时的答案。

于 2009-01-06T21:38:34.763 回答
5

使用将每个字节值 (256) 映射到其中 1 的数量的表。（0 的 # 只是（8 - 1 的 #））。然后遍历字节并对每个字节执行一次查找，而不是多次查找和比较。例如：

int onesCount = 0;
for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;
于 2009-01-06T21:42:13.713 回答
2

您可以使用预先计算的查找表，即：

static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */

...

for( ... ) 
   byte = ... 
   Stats.FreqOf1 += bitcount_lookup[byte];
于 2009-01-06T21:41:03.917 回答
2

我真的不明白你想做什么。但是，如果您只想访问位图的位，您可以使用这些（未经测试的！！！）函数：

#include <stddef.h>

_Bool isbitset(unsigned char * bitmap, size_t idx)
{
    return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}

void setbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] |= (1 << (idx % 8));
}

void unsetbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] &= ~(1 << (idx % 8));
}

void togglebit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] ^= (1 << (idx % 8));
}

编辑：好的，我想我明白你想要做什么：对一系列位进行快速迭代。因此，我们不想使用上面的随机访问函数，而是一次读取一个完整的数据字。

您可以使用任何您喜欢的无符号整数类型，但您应该选择一种可能与您的体系结构的字长相对应的类型。我会uint_fast32_t从stdint.h：

uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
    uint_fast32_t mask = 1;
    uint_fast32_t current = *data;
    for(; mask; mask <<= 1)
    {
        if(current & mask)
        {
            // bit is set
        }
        else
        {
            // bit is not set
        }
    }
}

在内部循环中，您可以使用

*data |= mask;

用

*data &= ~mask;

并用

*data ^= mask;

警告：代码在大端架构上可能会出现意外行为！

于 2009-01-06T23:00:08.733 回答
1

这是一种如何计算 32 位整数的 1 位的方法（基于 Java 的Integer.bitCount(i)方法）：

unsigned bitCount(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

因此，您可以将数据转换为 int 并以 4 个字节的步长向前移动。

于 2009-01-06T21:49:58.720 回答
1

这是一个简单的，我只使用一个 32 位值，但你可以看到它并不难适应任何数量的位......

int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
    if((x & 0x1) == 0x1) ones++;
    x = (x >> 1);
}

printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);

但是请注意，它会修改过程中的值。如果您要对需要保留的数据执行此操作，则需要先对其进行复制。

在 __asm 中执行此操作可能会更好，也许更快，但很难说编译器可以优化多少......

对于您考虑的每个解决方案，每个解决方案都会有缺点。查找表或移位器（如我的）都有缺点。

拉里

于 2009-01-06T22:04:14.447 回答
1

ttobiass - 请记住，您的内联函数在您所说的应用程序中很重要，但是您需要记住一些事情。您可以从内联代码中获得性能，只需记住几件事。

  • 调试模式下的内联不存在。（除非你强迫它）
  • 编译器将内联它认为合适的函数。通常，如果您告诉它内联一个函数，它可能根本不会这样做。即使你使用 __forceinline。有关内联的更多信息，请查看 MSDN。
  • 甚至只能内联某些函数。例如，您不能内联递归函数。

您将从 C/C++ 语言的项目设置以及构建代码的方式中获得最佳性能。此时，了解堆与堆栈操作、调用约定、内存对齐等很重要。

我知道这并不能完全回答您的问题，但是您提到了性能，以及如何获得最佳性能，这些都是关键。

于 2009-01-06T22:27:11.063 回答
0

加入链接车： 计数位

于 2009-01-06T21:43:17.907 回答
0

如果这不是过早优化的情况，并且您确实需要挤出最后的每一飞秒，那么您最好使用一个 256 元素的静态数组，用每个字节值的位数填充一次，然后

Stats.FreqOf1 += bitCountTable[字节]

当循环完成时：

Stats.FreqOf0 = ((data->Count * 8) - Stats.FreqOf1)

于 2009-01-06T21:47:09.117 回答
0

Beautiful Code一书中有一整章介绍了不同的技术。您可以从这里开始在 Google 图书上阅读（大部分）它。

于 2009-01-06T21:54:41.893 回答
0

一种更快的提取位的方法是使用：

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

如果您只想计算设置的位，那么每个缓存中的 LUT 会很快，但您也可以使用此答案链接中的交错位计数方法在恒定时间内完成。

于 2009-02-27T21:32:46.520 回答