From owner-freebsd-hackers@FreeBSD.ORG Thu Jun 11 14:50:16 2015 Return-Path: Delivered-To: freebsd-hackers@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 6FC0D313 for ; Thu, 11 Jun 2015 14:50:16 +0000 (UTC) (envelope-from ryao@gentoo.org) Received: from smtp.gentoo.org (smtp.gentoo.org [140.211.166.183]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 432A711B5 for ; Thu, 11 Jun 2015 14:50:15 +0000 (UTC) (envelope-from ryao@gentoo.org) Received: from [192.168.1.2] (pool-72-89-250-199.nycmny.fios.verizon.net [72.89.250.199]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) (Authenticated sender: ryao) by smtp.gentoo.org (Postfix) with ESMTPSA id 40A44340B78; Thu, 11 Jun 2015 14:50:07 +0000 (UTC) Message-ID: <5579A016.4040800@gentoo.org> Date: Thu, 11 Jun 2015 10:49:58 -0400 From: Richard Yao User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0 MIME-Version: 1.0 To: Erich Dollansky , "freebsd-hackers@freebsd.org" Subject: Re: allow ffs & co. a binary search References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> In-Reply-To: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="QQWswU3jpf8sjsFLUMgxAmaVKbCmIeGmK" X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 11 Jun 2015 14:50:16 -0000 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--