bitcounting 30000+位，但不是字节对齐 [英] bitcounting on 30000+ bits, but not byte aligned
问题描述
我有一个包含超过30000+位的数组。大小在
运行时变化。我需要经历这一段内存并经常计算一下这些内容。示例：前9位有2个，接下来10位有4个
，接下来9位有8个......我知道需要的位数是多少来自
到仅在运行时计算。但我知道这将是两个不同的长度连续数字，它可能只有一个长度，但是很少见。
。我知道长度在运行时进入的模式。
长度通常在32左右。我使用这个来使用盒式过滤器缩小大型1位图像的价值。不同长度来自DDA，它创建了一个过滤器，可以均匀地展开小盒子尺寸和大尺寸盒子大小的过滤器。所以我实际上会根据
图像的高度来做这个相同的30000次以上的
。速度非常重要。我不需要asm，因为它可以在不同的平台上运行
。我认为应该有一些方法来预先计算很多这个，因为所有行都将具有相同的模式
我需要计算的比特长度。我知道使用预先计算的
表来计算1个字节的位数，我相信它将是其中的一部分。
但是我还能预先计算什么以节省时间？谢谢。
I have an array that contains over 30000+ bits. The size varies at
runtime. I need to move through this chunk of memory and count bits
every so often. Example: First 9 bits has 2 ones, next 10 bits has 4
ones, next 9 bits has 8 ones ... I know the number of bits that need
to be counted at runtime only. But I do know it will be two different
lengths that are consecutive numbers, it could be just one length but
that will be rare. I know the pattern the lengths come in at runtime.
The lengths will normally be around 32. I am using this to scale
down large 1bit images using a box filter. The different lengths come
from a DDA that creates a filter that evenly spreads out the small box
size and large box size filter over the image. So I will actually do
this same bitcounting 30000+ times depending on the height of the
image. Speed is very important. I don''t need asm though since it
will run on different platforms. I think there should be some way to
precompute alot of this since all the rows will have the same pattern
of bit lenghts that I need to count. I know about using a precomputed
table for counting bits in 1 byte and I am sure that will part of it.
But what else can I precompute to save time? Thank you.
推荐答案
Eric 2004-06-24：
Eric 2004-06-24 :
我有一个包含的数组30000+位。
运行时的大小不同。我需要经常穿过这块内存并经常计算位数。例子：前9位有2位，接下来10位有4位，接下来9位有8位...我知道只需要在运行时计算的位数。但我知道这将是两个不同长度的连续数字，它可能只是一个长度但是很少见。我知道长度在运行时出现的模式。
长度通常在32左右。我使用它来使用盒式过滤器缩小大型1位图像。不同的长度来自DDA，它创建了一个过滤器，可以均匀地展开图像上的小盒子尺寸和大盒子大小的过滤器。所以我实际上会根据
图像的高度做同样的计数30000次。速度非常重要。我不需要asm，因为它将在不同的平台上运行。我认为应该有一些方法来预先计算很多这个，因为所有的行都具有我需要计算的相同长度的模式。我知道使用预先计算的表来计算1个字节的位数，我相信它将是其中的一部分。
但是我还能预先计算什么以节省时间？谢谢。
I have an array that contains over 30000+ bits. The size varies at
runtime. I need to move through this chunk of memory and count bits
every so often. Example: First 9 bits has 2 ones, next 10 bits has 4
ones, next 9 bits has 8 ones ... I know the number of bits that need
to be counted at runtime only. But I do know it will be two different
lengths that are consecutive numbers, it could be just one length but
that will be rare. I know the pattern the lengths come in at runtime.
The lengths will normally be around 32. I am using this to scale
down large 1bit images using a box filter. The different lengths come
from a DDA that creates a filter that evenly spreads out the small box
size and large box size filter over the image. So I will actually do
this same bitcounting 30000+ times depending on the height of the
image. Speed is very important. I don''t need asm though since it
will run on different platforms. I think there should be some way to
precompute alot of this since all the rows will have the same pattern
of bit lenghts that I need to count. I know about using a precomputed
table for counting bits in 1 byte and I am sure that will part of it.
But what else can I precompute to save time? Thank you.
我想你会在comp.graphics.algorithms中更多的话题，虽然
我会试着解释一下长度好一点，如果我是你，我就不会得到它，虽然我已经专业地进行了1位图像处理。
所有这一切都出现在我脑海中是：如果所有的零和/或所有的情况
都很频繁，那么在做其他任何事情之前处理它们。
BTW，我想你知道这个技巧计数位：
位= 0;
而（x）{
x& = x - 1;
bits ++;
}
Walter Tross
I guess you would be more on-topic in comp.graphics.algorithms, although
I would try to explain about the "lengths" a bit better, if I were you, I
didn''t get it, although I have done 1-bit image processing professionally.
All that comes to my mind is: if the all zeroes and/or the all ones cases
are frequent, handle them whith an if before doing anything else.
BTW, I guess you know this trick for counting bits:
bits = 0;
while (x) {
x &= x - 1;
bits++;
}
Walter Tross
为什么不使用查找表？
bits = lut [x]; // lut包含256个元素，x是一个字节
而不是
而（x）{
x & = x - 1;
bits ++;
}
Why don''t just use lookup table?
bits = lut[x]; // lut contains 256 elements and x is a byte
instead of
while (x) {
x &= x - 1;
bits++;
}
CFG 2004-06-25：
CFG 2004-06-25 :
为什么不只是使用查找表？
bits = lut [x]; // lut包含256个元素，x是一个字节
而不是
while（x）{
x& = x - 1;
bits ++;
}
Why don''t just use lookup table?
bits = lut[x]; // lut contains 256 elements and x is a byte
instead of
while (x) {
x &= x - 1;
bits++;
}
也许我不够清楚。我说BTW，我的意思是
主要用于构建查找表。它也可以代替
查找表，当已知非常罕见时（它实际上包括
if（！x）我将放在前面其余的如果不那么罕见）
Walter Tross
Maybe I was not clear enough. I said "BTW", and I meant the trick to be
used mainly to build the lookup table. It can also be used instead of the
lookup table when ones are known to be very rare (it practically includes
the if (!x) which I would put in front of the rest if ones are less rare)
Walter Tross
这篇关于bitcounting 30000+位，但不是字节对齐的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
