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 p4SLDn1q006833 for ; Sat, 28 May 2011 23:13:49 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AroFAEBl4U3RVdSykWdsb2JhbAA+AQMSG5dlMY4HCBQBAQEBCQsLBxQEIasFjB6CN4NEOYhiAQEDBoYYBJBPiyY7gzs X-IronPort-AV: E=Sophos;i="4.65,286,1304287200"; d="scan'208";a="109766170" Received: from mail-px0-f178.google.com ([209.85.212.178]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 28 May 2011 23:13:43 +0200 Received: by pxj25 with SMTP id 25so649448pxj.9 for ; Sat, 28 May 2011 14:13:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:date :message-id:subject:from:to:content-type:content-transfer-encoding; bh=apaJ3UkIcNpN/511gVlfpnpoj8fxaQKtXLBGUk5ZX78=; b=b+yzDzof75df9ByRrfwGCNUDJeurkSHywjAtAV0/IbpaHUqN+Ck3tJ711SFc5qjALa vuwdYXnA3c+oro1iaVT0/0IUYzRHKZ3P9UpKeD8k8VTCpw2Qy71xBesKefCjRjmYr5E4 bEWnL+JD/FJtyp2V1hHJxNqYygpA/TvuNYOm0= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=s7MZjlKPHgvIawlKZfY1xi2ZBeMDR2PKTfM9Kr5ByOBk2xtAEiKZsS7SZrn4Tonavt WxIzoBkH8gZm47ecB2zAORx3Zp/oUedTJm+QdCV7BdjuLUPNtrS7oRxCG91nUmBvfQpS U37VYEzqsEjsL3IvrqcyRnAOHUhRlfePmWVcM= MIME-Version: 1.0 Received: by 10.68.44.228 with SMTP id h4mr848675pbm.391.1306617221675; Sat, 28 May 2011 14:13:41 -0700 (PDT) Received: by 10.68.60.230 with HTTP; Sat, 28 May 2011 14:13:41 -0700 (PDT) In-Reply-To: References: <707567.2845.qm@web111505.mail.gq1.yahoo.com> <833816.58675.qm@web111502.mail.gq1.yahoo.com> <4DDFDC1F.5050605@inria.fr> <87y61qvhmo.fsf@fftw.org> Date: Sat, 28 May 2011 23:13:41 +0200 Message-ID: From: Johannes To: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p4SLDn1q006833 Subject: Fwd: [Caml-list] Re: Binary logarithm of a power of 2 A link to the de Bruijn paper can be found on the "Bit Twiddling Hacks" page linked earlyier in this thread: http://graphics.stanford.edu/~seander/bithacks.html I used it myself -- although with JavaScript and did not run any benchmarks -- and I liked the approach, very neat. 2011/5/28 Matteo Frigo : > 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 > > -- > 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 > >