Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!microsoft!gideony
From: gideony@microsoft.UUCP (Gideon YUVAL)
Newsgroups: comp.arch
Subject: Re: Compilers and efficiency
Message-ID: <72252@microsoft.UUCP>
Date: 9 May 91 18:57:41 GMT
References: <27fa3350.6bc2@petunia.CalPoly.EDU> <9782@mentor.cc.purdue.edu> <11411@mentor.cc.purdue.edu> <653@ctycal.UUCP> <STEPHEN.91May8001742@pesto.uchicago.edu>
Reply-To: gideony@microsoft.UUCP (Gideon YUVAL)
Organization: Microsoft Corp., Redmond WA
Lines: 13

In article <STEPHEN.91May8001742@pesto.uchicago.edu> stephen@pesto.uchicago.edu (Stephen P Spackman) writes:
>Are we talking about "find first one" here?
>
>Find first one was a pretty useful instruction in our lisp compiler.

If you start from the low-order bit, you can find the first "one"
bit by:

table[ (x  XOR (x-1)) MOD 37]

On a 386, this is 4X as fast (worst-case) as the "hardware" BSF.
-- 
Gideon Yuval, gideony@microsof.UUCP, 206-882-8080 (fax:206-883-8101;TWX:160520)