Algorithm Wanted
Tony Yule
algorithm for counting the number of bits set in a word was described. As I remember the
algorithm only involved logical operations and shifts; i.e. no loops were involved.
At the time the site operated a CDC 6600 computer which had an instruction which performed this
function. The operation was supported by the divide unit. (The 6600 had a number of units
that supported different types of operations.)
I have never seen this algorithm described and have been unable to reinvent it.
I apologise for posting this request here but it is the only newsgroup that I have been able
to find with "algorithm" in the title.
If anyone knows the algorithm I would be grateful of a description or a reference.
Otherwise if the newsgroup for such a request exists I would appreciate its name.
Replies to apy...@bcs.org.uk please.
Tony Yule I don't mind your thinking slowly:
apy...@bcs.org.uk I mind your publishing faster than you think.
Wolfgang Pauli (Attributed)
Ian Ashdown
>Twenty five years ago I attended a Lecture on aspects of programming. During the lecture an
>algorithm for counting the number of bits set in a word was described. As I remember the
>algorithm only involved logical operations and shifts; i.e. no loops were involved.
>
>At the time the site operated a CDC 6600 computer which had an instruction which performed this
>function. The operation was supported by the divide unit. (The 6600 had a number of units
>that supported different types of operations.)
>
>I have never seen this algorithm described and have been unable to reinvent it.
>
>I apologise for posting this request here but it is the only newsgroup that I have been able
>to find with "algorithm" in the title.
>
>If anyone knows the algorithm I would be grateful of a description or a reference.
>
>Otherwise if the newsgroup for such a request exists I would appreciate its name.
>
>Replies to apy...@bcs.org.uk please.
What you want is called "sideways addition." The naive approach is:
int NaiveSideSum( int val )
{
int temp = value;
int result = 0;
while (temp != 0)
{
result += temp & 0x01;
temp >> 1;
}
return result;
}
Nothing too exciting here. The worst-case performance of this
algorithm is N iterations of the WHILE loop (where N is the number of
bit positions in an integer). Of course, the maximum number for any
instance is determined by the most significant bit of the input value.
Fortunately, we can operate on multiple fields within the input value
simultaneously by first adding adjacent bits, then bit pairs, and so
on. This process, which involves "binary magic numbers," takes V
iterations in all cases, where V is the base-2 logarithm of N rounded
to the next highest integer.
Here's the function in C (with following explanations):
int FastSideSum( int value )
{
int i;
int result = value;
for (i = 0; i < V; i++)
result = ((result >> S[i]) & B[i]) + (result & B[i]);
return result;
}
Yes, there is still a loop involved. However, you can always unroll it
for any reasonable value of V. Thus for V = 4 (i.e, N = 16):
int SuperFastSideSum_16( int value )
{
int result = value;
result = ((result >> S[1]) & B[1]) + (result & B[1]);
result = ((result >> S[2]) & B[2]) + (result & B[2]);
result = ((result >> S[3]) & B[3]) + (result & B[3]);
result = ((result >> S[4]) & B[4]) + (result & B[4]);
return result;
}
If you look at the compiler output for these two functions and
calculate the number of machine cycles required for each, it becomes
evident that the binary magic number approach is preferable for large
N's.
Now, to explain S[] and B[]. The B array consists of binary magic
numbers, which are thoroughly discussed in:
Freed, Edwin E. 1983. "Binary Magic Numbers," Dr. Dobb's Journal
Vol. 78 (April), pp. 24-37.
Magic numbers in mathematics are numbers which have special or unusual
properties when used in certain calculations. Freed examined a class
of binary magic numbers that can be used to:
(a) Determine the positions of bits within words;
(b) Reverse, permute and map bits within words;
(c) Compute sideways (unweighted and weighted) sums and parity; and
(d) Convert Gray code values to their binary equivalents.
Binary magic numbers offer improved (i.e., faster) algorithms over
those that can otherwise be developed, typically by a factor of N /
log-2(N).
Freed's numbers are members of a sequence, where the Nth number of the
sequence is itself an infinite sequence from right to left of 2**N 1's
followed by 2**N 0's, followed 2**N 1's, and so on. The initial
numbers are:
...0101010101010101
...0011001100110011
...0000111100001111
...0000000011111111
...
For a word size of 16 bits then, we have four "B-constants":
B[1] = 0101010101010101
B[2] = 0011001100110011
B[3] = 0000111100001111
B[4] = 0000000011111111
There are three B-constants for words sizes (N) of 8 or fewer bits,
five B-constants for words sizes of 17 to 32 bits, and so on. As
mentioned above, N is the word size in bits, and V is the base-2
logarithm of N rounded to the next highest integer. B[1] through B[V]
are thus the binary magic numbers truncated to the N least-significant
bits, and V is:
N V
----------
8 3
9-16 4
17-32 5
33-64 6
...
The constants S[1] through S[N] are a table of the powers of 2. That
is:
S[1] = 2
S[2] = 4
S[3] = 8
S[4] = 16
...
About those CDC computers: According to Freed, the CDC 6400, 6500, and
6600 series processors had a "CXi Xk" instruction that counted the
number of nonzero bits in register Xk and stored the result in
register Xi. These were clearly CISC processors!
The binary magic numbers and associated algorithms that Freed
discusses are a godsend for anyone whose algorithms involve bit
twiddling. (One example of particular interest to computer graphics
mavericks is the bit reversal process required by the Fast Fourier
Transform and related algorithms.) Unfortunately, old back issues of
Dr. Dobb's Journal are *very* hard to find, and the DDJ Source Code
CD-ROM only goes back to 1986.
Freed (who was at the Mathematics Department of the Harvey Mudd
College in Claremont, California when he wrote his article)
acknowledged the assistance of Donald Knuth, and noted that many of
his algorithms were derived from the preprint version of Knuth's "The
Art of Computer Programming - Combinatorial Algorithms (Volume 4)."
Unless I missed it, however, this book was never published.
If anyone knows of another reference (one that is easier to find in a
good mathematics or computer science research lbrary, that is)
regarding binary magic numbers and their applications, I for one would
like to know about it :+)
(One paper of interest -- I wasn't aware of it myself until I began
writing this response -- may be:
Guibas, L., and J. Stolfi. 1981. "A Language for Bitmap
Manipulation," ACM Transactions on Graphics 1(3):192-214
which deals with transposing bit matrices. The paper likely refers to
previous papers on the topic.)
Dr. Dobb's Journal began life as "Dr. Dobb's Journal of Computer
Calisthenics & Orthdontia (Running Light Without Overbyte)." In
between discussions of CP/M games and Small C, it had some timeless
articles that are still worth their weight in gold. I'm glad I kept my
bsck issues!
Ian Ashdown, P. Eng. | READ THE BOOK!
Research & Development Manager | Radiosity: A Programmer's Perspective
Ledalite Architectural Products Inc. | by Ian Ashdown
| John Wiley & Sons, 1994
Visit http://www.ledalite.com | (Sneaky Internet Advertising)
Tony Yule
>
>Twenty five years ago I attended a Lecture on aspects of programming. During the lecture an
>algorithm for counting the number of bits set in a word was described. As I remember the
>algorithm only involved logical operations and shifts; i.e. no loops were involved.
>
>At the time the site operated a CDC 6600 computer which had an instruction which performed this
>function. The operation was supported by the divide unit. (The 6600 had a number of units
>that supported different types of operations.)
>
>I have never seen this algorithm described and have been unable to reinvent it.
>
Many thanks to all those who sent me algorithms for counting the number of bits
set in a word. The method that I was looking for was given to me by Frank A.
Vorstenbosch.
Fast bitcount:
#define BX_(x) ((x) - (((x)>>1)&0x77777777) \
- (((x)>>2)&0x33333333) \
- (((x)>>3)&0x11111111))
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
The modulo operation explains why the divide unit was employed.
An alternative solution was provided by Ian Ashdown. He has already posted his
article in the newsgroup so I will just repost the algorithm.
int bitcount (long x)
{static long b[] = {0x55555555, 0x33333333, 0x0f0f0f0f, 0x00ff00ff, 0x0000ffff};
static int s[] = {1, 2, 4, 8, 16};
int i;
for (i = 0; i < 5; i++)
x = ((x >> s[i]) & b[i]) + (x & b[i]);
return ((int) x);
}
A quick count of the number of operations needed gives
7 shifts, 7 ANDs, 7 additions/substractions and a divide for 1st method.
If we expand the loop in the second method we get
5 shifts, 10 ANDs, and 5 additions which I guess makes it a faster algorithm.
Andrea Griffini
>Twenty five years ago I attended a Lecture on aspects of programming. During the lecture an
>algorithm for counting the number of bits set in a word was described. As I remember the
>algorithm only involved logical operations and shifts; i.e. no loops were involved.
>At the time the site operated a CDC 6600 computer which had an instruction which performed this
>function. The operation was supported by the divide unit. (The 6600 had a number of units
>that supported different types of operations.)
>I have never seen this algorithm described and have been unable to reinvent it.
>I apologise for posting this request here but it is the only newsgroup that I have been able
>to find with "algorithm" in the title.
>If anyone knows the algorithm I would be grateful of a description or a reference.
>Otherwise if the newsgroup for such a request exists I would appreciate its name.
>Replies to apy...@bcs.org.uk please.
>Tony Yule I don't mind your thinking slowly:
>apy...@bcs.org.uk I mind your publishing faster than you think.
> Wolfgang Pauli (Attributed)
I don't know any such algorithm without loops... however there is a
well-know one that loops for the number of bits set (and not for the
word size); it's really nice and is quite often used as an example:
int Bits(int w)
{
int n;
for (n=0; w!=0; n++)
w&=w-1;
return n;
}
--------------------------------------------------_
Andrea Griffini agri...@vv.val.net \_
programmer a.gri...@agora.stm.it \_
http://vv.val.net/~agriffini \