From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p4SGI13C032612 for ; Sat, 28 May 2011 18:18:01 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArcCAPwe4U1iiyxykWdsb2JhbAA0CxYbl2WOVAEBAQEJCQ0HEieIca96AYxtBYYehmiOKSaKVg X-IronPort-AV: E=Sophos;i="4.65,286,1304287200"; d="scan'208";a="109758868" Received: from nm6-vm0.access.bullet.mail.sp2.yahoo.com ([98.139.44.114]) by mail1-smtp-roc.national.inria.fr with SMTP; 28 May 2011 18:17:55 +0200 Received: from [98.139.44.103] by nm6.access.bullet.mail.sp2.yahoo.com with NNFMP; 28 May 2011 16:17:53 -0000 Received: from [98.139.44.88] by tm8.access.bullet.mail.sp2.yahoo.com with NNFMP; 28 May 2011 16:17:53 -0000 Received: from [127.0.0.1] by omp1025.access.mail.sp2.yahoo.com with NNFMP; 28 May 2011 16:17:53 -0000 X-Yahoo-Newman-Id: 956031.1485.bm@omp1025.access.mail.sp2.yahoo.com Received: (qmail 42476 invoked from network); 28 May 2011 16:17:53 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s1024; t=1306599473; bh=Nf/v1LhRQ3el51agriyIm4Tg7+p0wJ7VV13vzG19ytE=; h=Received:X-Yahoo-SMTP:X-YMail-OSG:X-Yahoo-Newman-Property:Subject:Mime-Version:Content-Type:From:In-Reply-To:Date:Cc:Content-Transfer-Encoding:Message-Id:References:To:X-Mailer; b=cXz/iP5Dqw5hjZffFaBBuNmN6GUIEY0sHf1fcAYIb43qdoe3EZRkeCF/ai4G7zQazLIwl50JfkIFwesIhk5CAs+iFf1hHegUKfmJHXx9ICP/O4rawvjqoG/rBcBnidkg6q2AbsrnKvco+P1qS66G9YbP/ciVZ37z4gjBh3gb0/c= Received: from [192.168.1.67] (norm@99.4.121.168 with plain) by smtp106.sbc.mail.bf1.yahoo.com with SMTP; 28 May 2011 09:17:52 -0700 PDT X-Yahoo-SMTP: 6wM9MhqswBCJxy9jDcYebttHhXX021oP4RUg3aXahuvJwcSQLA-- X-YMail-OSG: xjwDxxgVM1n4eZGGosbP_tfJoPLerEm8X8mqOxi96ypYjIn Jdjyy6U7t1te31Oc7mhnLsqpr6jnJ9fSdvlvPVaJ.izl9BUzkxxTnCo5lX5b XOELHVj2P5Det81ubHDBvHHoNYSLhW4Q4NV0qrrrMuK4leaH_KNqKky6GMlc 2wLcBvRbGEL5BDxc5hQRQWK.orH08lY70uh7aphZnrv5zWec0_djsJvaRXWX cdrAIKaoDz1JVPXukFYXhGr5wIQEOmllgkQSIDTSEePD_d9KX8J1SfhzGMyF Y.TYZw_TNJ6F_Z7VqCvOnlLIgUHR01s.XeJCLh_mzeSjAAfulkJWr.f5fR3m cTkk2rM2IZMEjKt.6oydMwLGXeE6.5NyqSfHxn2jxDqXDPJOU9TTsHtMOFK9 xbpr84nS43tnsqpK_uQc91VaZJ46XBTyZJ8i1fZAI3JTxw4CLZhywTR.UTC5 B53ISj6.387u_UVfmyjh69oV89n7yC8mjr.7reJToXVOcf04ie1AnkXmUA94 riSTyzNU4o9gVnci3ghLQVzhxS5gt2a1BA4pTSyFEVMNsXn1jKOICCGstFI. H_vuM4t7Tycn8Az1Zx8NWhI465bAYGrcMkFQJy2WyyFI2lO_3cvegAVT5OEi nsbhVgg_bE66deE.nExv1xINDRnsrwnCZ4PQ49qSemqd1kHQD3AyGiznFq5r YFNs_eiUVAZYIIUxAs2LNQXlI4t7g3Vd8Vs8CA1Cm0N6M X-Yahoo-Newman-Property: ymail-3 Mime-Version: 1.0 (Apple Message framework v1084) Content-Type: text/plain; charset=us-ascii From: Norman Hardy In-Reply-To: <20110528052959.GA5839@kerneis.info> Date: Sat, 28 May 2011 09:17:51 -0700 Cc: Dario Teixeira , caml-list@inria.fr, Sylvain Le Gall Message-Id: References: <891579.63577.qm@web111515.mail.gq1.yahoo.com> <20110528052959.GA5839@kerneis.info> To: Gabriel Kerneis X-Mailer: Apple Mail (2.1084) Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p4SGI13C032612 Subject: Re: [Caml-list] Re: Binary logarithm of a power of 2 On 2011 May 27, at 22:29 , Gabriel Kerneis wrote: > On Fri, May 27, 2011 at 10:21:09AM -0700, Dario Teixeira wrote: >> Incidentally, I found a web page with lots of cool bit-twiddling hacks, >> which includes several solutions to the binary logarithm problem: >> http://graphics.stanford.edu/~seander/bithacks.html > > Some more of them: > http://www.cl.cam.ac.uk/~am21/hakmemc.html > > Those are the (famous) HAKMEM tricks, translated to C by Alan Mycroft. > Probably of no practical use, but learning what the fixed point of the float > function was on a PDP-10 is priceless... > > Best, > -- > Gabriel > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > In the spirit of HAKMEM here is a routine, in C, that counts the low zero bits of an integer less than 2^31: http://cap-lore.com/code/fb/ In machine language it might require just 7 instructions with no branches. I think that it cannot be improved to handle input greater than 2^31. A 63 bit version should be possible.