3695 views

Skip to first unread message

Feb 14, 1996, 3:00:00 AM2/14/96

to

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.

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)

Feb 15, 1996, 3:00:00 AM2/15/96

to

fw...@cityscape.co.uk (Tony Yule) wrote:

>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)

Feb 16, 1996, 3:00:00 AM2/16/96

to

In article <4ft4ng$l...@news.cityscape.co.uk>, fw...@cityscape.co.uk (Tony Yule) says:

>

>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.

>

>

>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.

Feb 18, 1996, 3:00:00 AM2/18/96

to

fw...@cityscape.co.uk (Tony Yule) wrote:

>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 \

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu