allow ffs & co. a binary search

[Hans Petter Selasky]

On 06/11/15 16:59, Richard Yao wrote:
> On 06/11/2015 10:52 AM, Ian Lepore wrote:
>> On Thu, 2015-06-11 at 10:49 -0400, Richard Yao wrote:
>>> On 06/06/2015 08:13 PM, Erich Dollansky wrote:
>> [...]
>>>
>>> The fastest portable way of calculating highest bit set is to use a
>>> debrujin sequence:
>>>
>>> https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
>>>
>>> The binary approach is inferior, especially on Pentium 4 processors.
>>
>> And of course it's crucial that we optimize for Pentium 4 processors in
>> 2015.
>
> The debrujin approach is fast regardless of the architecture. Anyway,
> this is a solved problem. There is no need to reinvent the wheel when
> the portable solutions are listed on that page at Stanford.
>

Hi Richard,

ffs() can be implemented like this simply:

int ffs_A(uint32_t v)
{
static const int MultiplyDeBruijnBitPosition[32] =
{
   0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
   8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v = ~(v - 1) & v;
return (MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]);
}


--HPS