From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p4SHp9Pq001997 for ; Sat, 28 May 2011 19:51:10 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0EAOM14U1Kfh5K/2dsb2JhbABVpkB3xWoOhhAEkE+PNg X-IronPort-AV: E=Sophos;i="4.65,286,1304287200"; d="scan'208";a="100052275" Received: from athena.fftw.org ([74.126.30.74]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/AES256-SHA; 28 May 2011 19:51:03 +0200 Received: from c-75-69-252-231.hsd1.nh.comcast.net ([75.69.252.231] helo=amd) by athena.fftw.org with esmtpsa (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.72) (envelope-from ) id 1QQNrE-0007u3-KG; Sat, 28 May 2011 14:03:28 -0400 Received: from athena by amd with local (Exim 4.72) (envelope-from ) id 1QQNf5-0006pM-Mj; Sat, 28 May 2011 13:50:55 -0400 From: Matteo Frigo To: Xavier Leroy Cc: caml-list@inria.fr References: <707567.2845.qm@web111505.mail.gq1.yahoo.com> <833816.58675.qm@web111502.mail.gq1.yahoo.com> <4DDFDC1F.5050605@inria.fr> Date: Sat, 28 May 2011 13:50:55 -0400 In-Reply-To: <4DDFDC1F.5050605@inria.fr> (Xavier Leroy's message of "Fri, 27 May 2011 19:15:11 +0200") Message-ID: <87y61qvhmo.fsf@fftw.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Subject: Re: [Caml-list] Re: Binary logarithm of a power of 2 A way exists to compute the binary logarithm with one multiplication and a couple of shifts. See Charles E. Leiserson, Harald Prokop, and Keith H. Randall: Using de Bruijn Sequences to Index a 1 in a Computer Word. The idea is that a magic 64-bit string of zeros and ones exists such that all possible strings of 6 bits appear as substrings of the string. Such a sequence is called a "de Bruijn Sequence". Let K be such a string interpreted as an int64. Then K * 2^n shifts K to the left by n places, leaving a unique encoding of n in the upper 6 bits of the product. Knuth Vol. 4A remarks that this is an old trick, invented but not published by some gentleman at IBM in the late sixties. (Sorry, I don't have Knuth at hand for an exact reference.) However the 1998 paper by Leiserson et al. should be available via google. Regards, Matteo Frigo