Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!news!bruce From: bruce@contingency.think.com (Bruce Walker) Newsgroups: comp.arch Subject: Re: new instructions Message-ID: Date: 23 May 91 23:19:37 GMT References: <24216@lanl.gov> <1991May23.192557.7558@kithrup.COM> <24263@lanl.gov> <1991May23.220143.8515@kithrup.COM> <1991May23.204624.22872@shograf.com> Sender: news@Think.COM Organization: Thinking Machines Corporation, Cambridge MA, USA Lines: 11 In-Reply-To: jimb@shograf.com's message of Thu, 23 May 1991 20:46:24 GMT As long as we are on the subject of bitcounting algorithms... One of my favorite toys is the fact that the expression "N & (N-1)" turns off the lowest order one-bit in N. Hence, it's a quick "find first", and can be made into a 4-cycle SPARC popcount loop which runs proportional to the number of ones (repeat N &= N-1 until N==0). I like the Poppen partial-sum algorithm, though. -- --Bruce Walker Thinking Machines Corporation, Cambridge, MA bruce@think.com; +1 617 234 4810; N1IKV