Re: Prime Program number of set bits Message #4 Posted by David Hayden on 23 Oct 2013, 3:05 p.m., in response to message #1 by kris223
There's a very fast algorithm for counting the number of bits. Suppose you have a 32 bit binary number n where each 16-bit half contains the number of bits that your starting number had in each half. You can add these two numbers together with:
tmp := BITSR(n,16);
n := BITAND(n, #0000FFFFh);
tmp := BITAND(tmp, #0000FFFFh);
n := n + tmp;
return n;
In a similar way, if n contains 4 fields of 8 bits each, you can add combine adjacent fields to form two 16 bit fields like this:
tmp := BITSR(n, 8);
n := BITAND(n, #00FF00FFh);
tmp := BITAND(tmp, #00FF00FFh);
n := n + tmp;
The idea can be extended all the way down to 1-bit fields. So the code to count the bits is:
EXPORT numsetbits(n)
BEGIN
LOCAL tmp;
tmp := BITSR(n);
n := BITAND(n, #55555555h);
tmp := BITAND(tmp, #55555555h);
n := n + tmp;
// n is now broken into fields of 2 bits
// each. Each field contains the number of
// bits that were set in it.
tmp := BITSR(n, 2);
n := BITAND(n, #33333333h);
tmp := BITAND(tmp, #33333333h);
n := n + tmp;
// now each field is 4 bits wide
tmp := BITSR(n, 4);
n := BITAND(n, #0F0F0F0Fh);
tmp := BITAND(tmp, #0F0F0F0Fh);
n := n + tmp;
// Fields are now 8 bits
tmp := BITSR(n, 8);
n := BITAND(n, #00FF00FFh);
tmp := BITAND(tmp, #00FF00FFh);
n := n + tmp;
tmp := BITSR(n,16);
n := BITAND(n, #0000FFFFh);
tmp := BITAND(tmp, #0000FFFFh);
n := n + tmp;
return n;
END;
|