From - Wed Sep 10 09:43:37 1997
Path: news.mitre.org!blanket.mitre.org!agate!newsgate.cuhk.edu.hk!logbridge.uoregon.edu!su-news-hub1.bbnplanet.com!cpk-news-hub1.bbnplanet.com!news.bbnplanet.com!newsfeed.nacamar.de!oleane!pasteur.fr!jussieu.fr!univ-angers.fr!univ-rennes1.fr!irisa.fr!news-rocq.inria.fr!pauillac.inria.fr!harley
From: harley@pauillac.inria.fr (Robert Harley)
Newsgroups: comp.arch
Subject: Re: [++] Re: {left|right}most set bit...
Date: 10 Sep 1997 13:12:57 GMT
Organization: I.N.R.I.A Rocquencourt
Lines: 36
Message-ID: <5v66cp$4qd@news-rocq.inria.fr>
NNTP-Posting-Host: pauillac.inria.fr
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit

This thread again!

Terje wrote:
>I received email from Tom Rokicki, who can't post, so I'll make an update
>with his idea:
>>[...]
>>    (a & -a) * 0x1d0d73df
>> 
>> has the top six bits indicating find-least-bit
>> suitable for indexing a table.  No comparisons

This is what was suggested last time around too, except that it may be
best to find a multiplier that can be done quickly with shifts and adds.
This takes 7 cycles on ARM:

signed char twos(u32 n) {
  static const signed char tab[64] =
  { -1, 0, 1, 12, 2, 6, 0, 13, 3, 0, 7, 0, 0, 0, 0, 14 , 10, 4, 0, 0
  , 8, 0, 0, 25, 0, 0, 0, 0, 0, 21, 27 , 15, 31, 11, 5, 0, 0, 0, 0, 0
  , 9, 0, 0, 24, 0, 0 , 20, 26, 30, 0, 0, 0, 0, 23, 0, 19, 29, 0, 22
  , 18, 28, 17, 16, 0
  };

  n &= ~(n-1UL);
  n = (n<<16)-n;
  n = (n<<6)+n;
  n = (n<<4)+n;

  return tab[n>>26];
} /* end twos */

The result is the index 0..31 of the least set bit, or -1 if none.
For 64-bit numbers multiply by (2^32-1)*(2^11+1)*(2^6-1)*(2^5-1)*(2^3+1),
define tab[128] accordingly and return tab[n>>57].

-- Rob.
