Re: finding rightmost zero bit

ttw@xxxxxxxxxxxxxxx wrote:

For a chess-playing program I found the following the fastest. First,
check if N>2**32 then check against the 2**16 and 3*2**16; continue
down to 8 bits. (Using a binary search this takes only 3 tests.) This
gives a partial answer. The previous answer is then completed by taking
the unknown byte and using a table lookup: 00000000=1, 000000001=1,
00000010=2,00000011=1, etc. A similar method was fastest for leading 1
bits.


I thought about one like that, but it wasn't so easy to get the
bytes out of an integer in standard Fortran, and probably even
harder in F.  Doing it with shifts takes enough more than I was
otherwise doing that I didn't try it.  Though it depends much on
the cost of the conditional branch or conditional load, so I
can't really say.  But yes, in general I prefer table lookups.

-- glen

.

Relevant Pages

  • Re: last number array from string
    ... >HLOOKUP, VLOOKUP, LOOKUP return incorrect values in Excel ... range specified for the "lookup_vector" argument (VLOOKUP and HLOOKUP) ... For binary search to work, the arrays must be sorted, usually ...
    (microsoft.public.excel.worksheet.functions)
  • Re: old interview question: function that returns country code when given an ip address
    ... I'd start with the binary search solution, ... would contain the indices into the list of sorted country code / IP ... a lookup table. ... with binary search. ...
    (comp.programming)
  • Re: Optimized binary search?
    ... One of the issues is this lookup function. ... I think it ran at 16 MHz, and some instructions took 32 cycles to ... whatever it is called should be completed in 1 cycle. ... Since the binary search jumps, dividing the table in half, i think the L1 ...
    (borland.public.delphi.language.basm)
  • Re: best collection to use for fast lookups
    ... > This collection will be used to lookup objects based on a few string ... binary search on a sorted list. ... If you CAN specify the exact desired data ... > Array.binarySearch (and the Comparator again) method to perform the ...
    (comp.lang.java.programmer)
  • Re: Extreamly large Hashtable
    ... be the fastest way of accessing in-memory data of such a large list of values. ... Hashtables can be made O, whereas binary lookup is O. ... It is also not generally true that binary searching is used as part of looking up data via a hash table. ... Furthermore, I'm uncertain whether you did not understand Chris comments about asymptotic complexity or whether you simply chose to ignore them, but they are irrefutable: in the limit of many data and given a reasonable hashing function, a hash table will *always* outperform a binary search. ...
    (comp.lang.java.programmer)