Comment #0 by bearophile_hugs — 2010-08-23T17:26:32Z
The method sort() of std.bitmanip.BitArray doesn't look so useful, and it may be removed.
On the other hand there is some very commonly useful functionality that it is missing in BitArray:
1) b[] = 0; and b[] = 1; to set and reset the whole array quickly, this is a very common need.
2) countSet(): returns the number of bits set inside the bit array.
3) flip(n): to invert the state of the n-th bit of the bit array.
4) set(n): to set (to 1) the n-th bit of the bit array.
5) reset(n): to reset (set to 0) the n-th bit of the bit array.
6) flipAll(): to invert the state of all bits of the bit array.
7) toSting(): that converts the bit array into a string like "BitArray(\"0101010011001\")".
8) this() (constructor) method that builds a bit array from a string like "0101010011001", it's the opposite of the toString().
Optionally:
9) Basic Range interface for the BitArray, so you may use map() on it.
10) firstSet(): returns the index of the first bit that is set, starting the search from the less significant bit. This is for more specialized usage, like some heaps.
Notes:
- The count() is also known known as Population or Hamming weight. This is useful for Hamming distances, to count bits in many situations, like for example for the Sieve of Eratosthenes. There are ways and refined algorithms to speed up this operation a lot. And this is a very commonly useful operation. I may offer some D code if you want. See also:
http://en.wikipedia.org/wiki/Hamming_weighthttp://graphics.stanford.edu/~seander/bithacks.html
And see also the __builtin_popcount() built-in function of GCC.
- The flip(n), set(n) and reset(n) methods are useful because they may be made more efficient than opIndexAssign().
- Regarding firstSet(), see also the __builtin_ffs() built-in function of GCC.
- Methods like opXorAssign() probably need to be converted to the new operator overloading of D2.
Comment #1 by bearophile_hugs — 2010-08-23T17:38:53Z
As alternative flipAll() may be named flip() (with no arguments).
Comment #2 by clugdbug — 2010-08-24T00:33:44Z
(In reply to comment #0)
> - The count() is also known known as Population or Hamming weight. This is
> useful for Hamming distances, to count bits in many situations, like for
> example for the Sieve of Eratosthenes. There are ways and refined algorithms to
> speed up this operation a lot. And this is a very commonly useful operation. I
> may offer some D code if you want. See also:
> http://en.wikipedia.org/wiki/Hamming_weight
> http://graphics.stanford.edu/~seander/bithacks.html
> And see also the __builtin_popcount() built-in function of GCC.
Curious fact: the built-in popcount instruction isn't much use for bit arrays. It's great for 64 bit longs (especially for chess programs!) but once you have a dozen machine words or more, it's faster to add the bits sideways. An interesting consequence of this is that Intel/AMD's new popcount instruction is hardly ever useful...
Comment #3 by bearophile_hugs — 2010-08-24T03:57:46Z
Answer to Comment 2:
The code in the bithacks site I have given URL of probably is what you were talking about.
But then there are refined algorithms to use the basic code shown in bithacks, that becomes useful as the bit array gets a little larger.
Comment #4 by clugdbug — 2010-08-24T05:55:05Z
(In reply to comment #3)
> Answer to Comment 2:
> The code in the bithacks site I have given URL of probably is what you were
> talking about.
> But then there are refined algorithms to use the basic code shown in bithacks,
> that becomes useful as the bit array gets a little larger.
No, that's not what I meant at all. The parallel adding I'm referring to does not involve any shifts.
You basically implement a half adder. Given 2 words a, b the low bit of the sum is a^b, and the high bit is a&b.
And with 3 words a, b, c, the low bit of the sum is a^b^c and the high word is (a&b)|((a^b)&c). The popcount is popcount(lo word) + 2* popcount(high word).
So what you do is pass through the array in pairs, grabbing the values a, b. You accumulate popcount p += 2*popcount((a&b)|((a^b)&c)). calculate a new carry c = a^b^c. Then you add p+=popcount(c); at the end. In this way, you've dealt with two words, but only done one single-word popcount.
In practice, you don't just use pairs, you grab 8 or 16 values at a time, and keep a 3 or 4 bit sum. You only have to perform one single-word popcount for every 8 or 16 words. You need to do a lot of logical operations, but they pipeline quite well.
Comment #5 by bearophile_hugs — 2010-08-24T06:31:52Z
I see, I think you are talking about using a SWAR approach then. I have never used it for this job, but it sounds intersting. I'd like to do some benchmarks to see what the most efficient solution is among those two.
It looks like a simple problem, but has a surprisingly high number of interesting solutions.
Comment #6 by bearophile_hugs — 2010-08-24T14:02:31Z
For efficiency on 64 bit systems too you may change this code from the BitArray struct:
struct BitArray
{
size_t len;
uint* ptr;
...
void init(void[] v, size_t numbits)
in
{
assert(numbits <= v.length * 8);
assert((v.length & 3) == 0);
}
Into:
struct BitArray
{
size_t len;
size_t* ptr; // changed here
...
void init(void[] v, size_t numbits)
in
{
assert(numbits <= v.length * 8);
assert(v.length % size_t.sizeof == 0); // changed here
}
Comment #7 by clugdbug — 2010-08-25T01:47:59Z
(In reply to comment #5)
> I see, I think you are talking about using a SWAR approach then. I have never
> used it for this job, but it sounds intersting. I'd like to do some benchmarks
> to see what the most efficient solution is among those two.
> It looks like a simple problem, but has a surprisingly high number of
> interesting solutions.
Found the link:
http://www.icis.ntu.edu.sg/scs-ijit/91/91-1.pdf
Comment #8 by bearophile_hugs — 2010-08-26T07:56:20Z
See also bug 4124 and bug 4123
Comment #9 by bearophile_hugs — 2010-09-22T12:24:24Z