Date: Thu, 11 Jun 2015 10:49:58 -0400 From: Richard Yao <ryao@gentoo.org> To: Erich Dollansky <erichsfreebsdlist@alogt.com>, "freebsd-hackers@freebsd.org" <freebsd-hackers@FreeBSD.org> Subject: Re: allow ffs & co. a binary search Message-ID: <5579A016.4040800@gentoo.org> In-Reply-To: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com>
next in thread | previous in thread | raw e-mail | index | archive | help
This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--QQWswU3jpf8sjsFLUMgxAmaVKbCmIeGmK
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
On 06/06/2015 08:13 PM, Erich Dollansky wrote:
> Hi,
>=20
> I stumbled these days over the functions to find the first or last bit
> set. They are currently written like this:
>=20
> /*
> * Find First Set bit
> */
> int
> ffs(int mask)
> {
> int bit;
>=20
> if (mask =3D=3D 0)
> return (0);
> for (bit =3D 1; !(mask & 1); bit++)
> mask =3D (unsigned int)mask >> 1;
> return (bit);
> }
>=20
> With other words, the program loops until it finds what it searches for=
=2E
>=20
> Why not do it the binary way?
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.
Just my two cents.
>=20
> int res;
>=20
> res =3D 0;
> IF (Number !=3D 0) THEN
> res =3D 1;
> IF ((Number & 0xFFFFFFFF00000000) !=3D 0) THEN
> Number =3D Number & 0xFFFFFFFF00000000;
> res =3D res + 32;
> END;
> IF ((Number & 0xFFFF0000FFFF0000) !=3D 0) THEN
> Number =3D Number & 0xFFFF0000FFFF0000;
> res =3D res + 16;
> END;
> IF ((Number & 0xFF00FF00FF00FF00) !=3D 0) THEN
> Number =3D Number & 0xFF00FF00FF00FF00;
> res =3D res + 8;
> END;
> IF ((Number & 0xF0F0F0F0F0F0F0F0) !=3D 0) THEN
> Number =3D Number & 0xF0F0F0F0F0F0F0F0;
> res =3D res + 4;
> END;
> IF ((Number & 0xCCCCCCCCCCCCCCCC) !=3D 0) THEN
> Number =3D Number & 0xCCCCCCCCCCCCCCCC;
> res =3D res + 2;
> END;
> IF ((Number & 0xAAAAAAAAAAAAAAAA) !=3D 0) THEN
> Number =3D Number & 0xAAAAAAAAAAAAAAAA;
> res =3D res + 1;
> END;
> END;
> return res;
>=20
> If you like the binary way I could give you the sources for the
> complete family following your style to replace the older functions.
>=20
> Erich
> _______________________________________________
> freebsd-hackers@freebsd.org mailing list
> http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
> To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.o=
rg"
>=20
--QQWswU3jpf8sjsFLUMgxAmaVKbCmIeGmK
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2
iQIcBAEBAgAGBQJVeaAZAAoJECDuEZm+6ExkNAYP/j1bHAYCDcaH7uIL2Ur9+Uck
tOu8NKXY7L2U5oMXcDTaBIhlGGrAv2vmZl+Owdnwl7BqQ+igmYWtCvLN7KNB6Ok+
bnhUxunbyaWRgMKZMM3gWg3tICOcR4HAYjZR3qa0kXZplkWKJB1i9s6oXSvkN7Tr
dzMESl+VfU8noE8nmhLCw4MVcmnjTEBfeXkeXjhJb38Go7Ed17zZoGWIbo1KyJ5p
vtpe46NEXVL1htpCIR4Ck/dfOlzwNvbk7s+MoySuvKEWd27SWKyaopuyEDc969le
Dbi3tv3yuNcvG6dOx4gq83DlPw8jZ86gjwMVKE1NBfTco/hGQrouv3MMttIDqHkE
jobE+Fic+bSO+efVNqis+5gAwvEMMAeUhl+kM5hVbqBsDcFvisuwfFatXPYLYN7s
iiy9Sw52wNog7eTll2ihH+ZFV/DcVlFam8pKynJZqk4hcKaubfGIy8/zeP75zmWn
Iyh1sAMxkeHAopnL0DssKFD/sme51AcMmNlGV3UgYOz+Mpgw+Op2UhklR73NtaZp
p6iEL2rBqWqW8Iz1cZ4sUrXYDfUgaKAVHheByga9KSEAIufyNGvBaWm8jpL14XVT
SZ/cUpbPnNUM1Z8EtQS+h1Oq3OKvi8tQlO5qz+EDtPJJLd9dKnBpjxoAl5Qddtmn
fpmj4nAQ+9a8JjNyd3cx
=bvyf
-----END PGP SIGNATURE-----
--QQWswU3jpf8sjsFLUMgxAmaVKbCmIeGmK--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?5579A016.4040800>