Date: Fri, 12 Jun 2015 03:59:15 +0200 From: Hans Petter Selasky <hps@selasky.org> To: Richard Yao <ryao@gentoo.org>, Ian Lepore <ian@freebsd.org> Cc: "freebsd-hackers@freebsd.org" <freebsd-hackers@FreeBSD.org>, Erich Dollansky <erichsfreebsdlist@alogt.com> Subject: Re: allow ffs & co. a binary search Message-ID: <557A3CF3.3050603@selasky.org> In-Reply-To: <5579A235.80609@gentoo.org> References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5579A016.4040800@gentoo.org> <1434034373.1415.3.camel@freebsd.org> <5579A235.80609@gentoo.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?557A3CF3.3050603>