Xref: utzoo comp.lang.c:15385 comp.std.c:661
Path: utzoo!utgpu!watmath!clyde!ima!think!barmar
From: barmar@think.COM (Barry Margolin)
Newsgroups: comp.lang.c,comp.std.c
Subject: Re: BIT Counting: C programming problem
Message-ID: <35329@think.UUCP>
Date: 11 Jan 89 09:42:19 GMT
References: <225@tityus.UUCP>
Sender: news@think.UUCP
Reply-To: barmar@kulla.think.com.UUCP (Barry Margolin)
Organization: Thinking Machines Corporation, Cambridge MA, USA
Lines: 23

I haven't seen anyone so far suggest the far end of the time/space
trade-off: have a 64K table, with each element N containing the number
of bits in N (you'll probably have to use one of the slower mechanisms
to compute the contents of this table, but it only needs to be run
once when writing the program and then incorporated into the program
text as an initial value).  Someone else came close by suggesting a
256-element table which would be consulted twice and then the results
added.  But is an extra 64Kbytes of data much of a problem in these
days of large and/or virtual memories?

One argument against this in a paging environment is that this is more
likely to cause a page fault than other mechanisms that use less data
and more computation, and a page fault is at least an order of
magnitude more expensive than arithmetic instructions.  And in
swapping systems it will increase process loading time.  But on 1Mb PC
it's only 6% of your memory capacity, and it might be worth it
depending on the application.

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar