[Issue 4717] std.bitmanip.BitArray changes

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=4717



--- Comment #4 from Don <clugdbug at yahoo.com.au> 2010-08-24 05:55:05 PDT ---
(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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------