http://d.puremagic.com/issues/show_bug.cgi?id=4717
--- Comment #4 from Don <clugd...@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: -------
