Path: utzoo!utgpu!attcan!uunet!seismo!sundc!pitstop!sun!decwrl!nsc!taux01!taux02!yuval
From: yuval@taux02.UUCP (Gideon Yuval)
Newsgroups: comp.arch
Subject: Re: RISC v. CISC --more misconceptions
Summary: "find 1st bit" needs NO special H/W
Message-ID: <232@taux02.UUCP>
Date: 3 Nov 88 06:25:00 GMT
References: <156@gloom.UUCP> <18931@apple.Apple.COM> <40@sopwith.UUCP> <998@l.cc.purdue.edu> <7575@aw.sei.cmu.edu> <23449@amdcad.AMD.COM>
Reply-To: yuval@taux02.UUCP (Gideon Yuval)
Organization: National Semiconductor (IC) Ltd, Israel
Lines: 18


If you want to find the first (bottom) "1" bit in a machine word X, try:

table [  (X xor (X-1)) mod 37 ] 

Proof is left as an exercise for the reader, as is contruction of the array 
"table".

Thus, any machine that can implement "C" can do "find first bit" with
reasonable efficiency.

N.B. On a 16-bit CPU, replace 37 by 19.

(I replaced "^" by "xor", and "%" by "mod", to avoid illegibility).
-- 
Gideon Yuval, yuval@taux01.nsc.com, +972-2-690992 (home) ,-52-522255(work)
 Paper-mail: National Semiconductor, 6 Maskit St., Herzliyah, Israel
                                                TWX: 33691, fax: +972-52-558322