a bit of a puzzle

Discussion in 'C Programming' started by Steven G. Johnson, Mar 9, 2008.

  1. Here is a little algorithm I came across whose implementation is
    amusingly obscure: what simple function does the following C code
    compute, and why?

    #include <stdint.h>
    unsigned foo(uint32_t n)
    {
    const uint32_t a = 0x05f66a47;
    static const unsigned bar[32] =
    {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,10,29,9,8,7};
    n = ~n;
    return bar[(a * (n & (-n))) >> 27];
    }

    To save you the trouble of compiling and running it yourself, here is
    what it produces for n = 0,1,2,...,31:

    0 -> 0, 1 -> 1, 2 -> 0, 3 -> 2, 4 -> 0, 5 -> 1, 6 -> 0, 7 -> 3, 8 ->
    0, 9 -> 1, 10 -> 0, 11 -> 2, 12 -> 0, 13 -> 1, 14 -> 0, 15 -> 4, 16 ->
    0, 17 -> 1, 18 -> 0, 19 -> 2, 20 -> 0, 21 -> 1, 22 -> 0, 23 -> 3, 24 -
    > 0, 25 -> 1, 26 -> 0, 27 -> 2, 28 -> 0, 29 -> 1, 30 -> 0, 31 -> 5
     
    Steven G. Johnson, Mar 9, 2008
    #1
    1. Advertising

  2. Steven G. Johnson said:

    <snip>

    > To save you the trouble of compiling and running it yourself, here is
    > what it produces for n = 0,1,2,...,31:
    >
    > 0 -> 0, 1 -> 1, 2 -> 0, 3 -> 2, 4 -> 0, 5 -> 1, 6 -> 0, 7 -> 3, 8 ->
    > 0, 9 -> 1, 10 -> 0, 11 -> 2, 12 -> 0, 13 -> 1, 14 -> 0, 15 -> 4, 16 ->
    > 0, 17 -> 1, 18 -> 0, 19 -> 2, 20 -> 0, 21 -> 1, 22 -> 0, 23 -> 3, 24 -
    >> 0, 25 -> 1, 26 -> 0, 27 -> 2, 28 -> 0, 29 -> 1, 30 -> 0, 31 -> 5


    Obviously I can't tell what the algorithm is actually used for, but it is
    isomorphic to the following usage: the Nth number represents the number of
    levels beneath the Nth item discovered in a perfectly balanced binary tree
    during a postorder traversal (left, centre, right).

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Mar 9, 2008
    #2
    1. Advertising

  3. On Mar 9, 1:58 pm, Richard Heathfield <> wrote:
    > Obviously I can't tell what the algorithm is actually used for, but it is
    > isomorphic to the following usage: the Nth number represents the number of
    > levels beneath the Nth item discovered in a perfectly balanced binary tree
    > during a postorder traversal (left, centre, right).


    There is a simpler, purely arithmetic definition of what it computes.

    By "why?" I don't mean "why was this particular code
    written" (obviously unanswerable) but "why does it compute what it
    does for all n (once you figure out what it does)?" i.e., how does it
    work?
     
    Steven G. Johnson, Mar 9, 2008
    #3
  4. On Sun, 09 Mar 2008 10:40:50 -0700, Steven G. Johnson wrote:
    > Here is a little algorithm I came across whose implementation is
    > amusingly obscure: what simple function does the following C code
    > compute, and why?
    >
    > #include <stdint.h>
    > unsigned foo(uint32_t n)
    > {
    > const uint32_t a = 0x05f66a47;
    > static const unsigned bar[32] =
    >

    {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,10,29,9,8,7};

    > n = ~n;
    > return bar[(a * (n & (-n))) >> 27];


    n = ~n;
    n = a * (n & -n);
    return bar[n >> 27];

    You're assuming that the multiplication (a * (n & (-n))) will take place
    in 32 bits. This is not the case when int or unsigned int has more than
    32 bits. Store the result in n to be sure.

    > }
    >
    > To save you the trouble of compiling and running it yourself, here is
    > what it produces for n = 0,1,2,...,31:
    >
    > 0 -> 0, 1 -> 1, 2 -> 0, 3 -> 2, 4 -> 0, 5 -> 1, 6 -> 0, 7 -> 3, 8 -> 0,
    > 9 -> 1, 10 -> 0, 11 -> 2, 12 -> 0, 13 -> 1, 14 -> 0, 15 -> 4, 16 -> 0,
    > 17 -> 1, 18 -> 0, 19 -> 2, 20 -> 0, 21 -> 1, 22 -> 0, 23 -> 3, 24 -
    >> 0, 25 -> 1, 26 -> 0, 27 -> 2, 28 -> 0, 29 -> 1, 30 -> 0, 31 -> 5


    This looks like the number of consecutive bits set, starting from the
    least significant.

    (~n) & (-~n) can be written as (n + 1) & ~n. It is the value of the
    lowest bit that is not set. The multiplication by 0x05f66a47 happens to
    produce unique values in bits 27-31 for the first 32 powers of two (I'm
    not seeing how this value was obtained), so after extracting those bits,
    you can use a lookup table to find the result.
     
    Harald van Dijk, Mar 9, 2008
    #4
  5. Just to be clear, I know what it does and how it works; I'm not asking
    for programming help. I'm posing it as a puzzle for amusement and
    edification.

    Background:

    It's a C implementation of an algorithm I found in a rather famous
    book, for a rather simple and important arithmetic problem (which
    shows up as a subproblem in Gray codes, low-discrepancy sequences, and
    many other problems), and is one of the fastest and most compact
    solutions to this problem that I could find (without using assembly)
    (although there is one slightly faster method on my machine that is
    not so compact).

    What I found amusing is that, if you don't comment the code, it seems
    quite nonobvious what this algorithm computes, and even if you deduce
    that from the function outputs it seems very nonobvious why/how it
    works.

    Regards,
    Steven G. Johnson
     
    Steven G. Johnson, Mar 9, 2008
    #5
  6. Steven G. Johnson

    CBFalconer Guest

    "Steven G. Johnson" wrote:
    >
    > Here is a little algorithm I came across whose implementation is
    > amusingly obscure: what simple function does the following C code
    > compute, and why?
    >
    > #include <stdint.h>
    > unsigned foo(uint32_t n)
    > {
    > const uint32_t a = 0x05f66a47;
    > static const unsigned bar[32] =
    > {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,10,29,9,8,7};
    > n = ~n;
    > return bar[(a * (n & (-n))) >> 27];
    > }


    Doesn't seem to work very well on a machine with 16 bit integers.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Mar 10, 2008
    #6
  7. On Mar 9, 2:31 pm, Harald van D©¦k <> wrote:
    > (~n) & (-~n) can be written as (n + 1) & ~n. It is the value of the
    > lowest bit that is not set. The multiplication by 0x05f66a47 happens to
    > produce unique values in bits 27-31 for the first 32 powers of two (I'm
    > not seeing how this value was obtained), so after extracting those bits,
    > you can use a lookup table to find the result.


    Yes, the algorithm is described in Knuth volume 4A (draft fascicle)
    section 7.1.3 ("Bitwise tricks and techniques"), who attributes it
    Lauter and others in 1997. The main trick is the magic constant
    "0x05f66a47"; Knuth describes the properties it requires (related to
    de Bruijn) cycles, and the fact that there are many such constants
    that will work; this particular one was found by a brute-force search.

    It's a cute and compact way of finding the number of rightmost-1 bits
    (or rightmost-zero bits, without the ~n). A slightly (~15%) faster
    way (but less compact), at least on my machine, is to search the bytes
    of ~n, starting from the least-significant byte, until a nonzero byte
    is found, and then use a 256-element lookup table...this has slower
    worst-case performance (for cases where the rightmost zero bit is in
    the most significant byte), but slightly better average-case
    performance (YMMV) (since a random number has a 255/256 chance of
    having its rightmost zero in the least-significant byte). Of course,
    on processors like x86 you can do faster in assembly, or with gcc's
    __builtin_ctz function, but it's a fun little puzzle to do this as
    fast and/or as compactly as possible in plain C.

    Steven
     
    Steven G. Johnson, Mar 10, 2008
    #7
  8. CBFalconer <> writes:
    > "Steven G. Johnson" wrote:
    >> Here is a little algorithm I came across whose implementation is
    >> amusingly obscure: what simple function does the following C code
    >> compute, and why?
    >>
    >> #include <stdint.h>
    >> unsigned foo(uint32_t n)
    >> {
    >> const uint32_t a = 0x05f66a47;
    >> static const unsigned bar[32] =
    >> {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,10,29,9,8,7};
    >> n = ~n;
    >> return bar[(a * (n & (-n))) >> 27];
    >> }

    >
    > Doesn't seem to work very well on a machine with 16 bit integers.


    Most machines have 16-bit integers; often the 16-bit integer type is
    called "short".

    If you mean 16-bit ints, I don't see how that would cause a problem,
    since the fucntion's argument is of type uint32_t. (The unsigned
    result shouldn't be a problem unless you're worried about integers
    with more than 32767 bits.)

    Or am I missing something?

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Mar 10, 2008
    #8
  9. Steven G. Johnson

    CBFalconer Guest

    Keith Thompson wrote:
    > CBFalconer <> writes:
    >> "Steven G. Johnson" wrote:

    >
    >>> Here is a little algorithm I came across whose implementation is
    >>> amusingly obscure: what simple function does the following C code
    >>> compute, and why?
    >>>
    >>> #include <stdint.h>
    >>> unsigned foo(uint32_t n) {
    >>> const uint32_t a = 0x05f66a47;
    >>> static const unsigned bar[32] =
    >>> {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,10,29,9,8,7};
    >>> n = ~n;
    >>> return bar[(a * (n & (-n))) >> 27];
    >>> }

    >>
    >> Doesn't seem to work very well on a machine with 16 bit integers.

    >
    > Most machines have 16-bit integers; often the 16-bit integer type is
    > called "short".
    >
    > If you mean 16-bit ints, I don't see how that would cause a problem,
    > since the fucntion's argument is of type uint32_t. (The unsigned
    > result shouldn't be a problem unless you're worried about integers
    > with more than 32767 bits.)
    >
    > Or am I missing something?


    Yeah, I meant int, and was sloppy. To me, uint32_t doesn't exist,
    since it is not guaranteed. Lets make the complaint about a
    machine with an 18 bit int.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Mar 10, 2008
    #9
  10. CBFalconer wrote:
    > "Steven G. Johnson" wrote:
    >>
    >> Here is a little algorithm I came across whose implementation is
    >> amusingly obscure: what simple function does the following C code
    >> compute, and why?
    >>
    >> #include <stdint.h>
    >> unsigned foo(uint32_t n)
    >> {
    >> const uint32_t a = 0x05f66a47;
    >> static const unsigned bar[32] =
    >> {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,10,29,9,8,7};
    >> n = ~n;
    >> return bar[(a * (n & (-n))) >> 27];
    >> }

    >
    > Doesn't seem to work very well on a machine with 16 bit integers.

    Mind to enlighten me why?

    Bye, Jojo
     
    Joachim Schmitz, Mar 10, 2008
    #10
  11. Steven G. Johnson

    Gerry Ford Guest

    I'll admit to the non-obviousness. Would you state its relevance to
    X.690-0207.pdf ?

    --
    Gerry Ford



    "Anybody who says, that a high-speed collision with water is the same as
    with concrete, likely has more experience with the former than the latter."
    "Steven G. Johnson" <> wrote in message
    news:...
    > Just to be clear, I know what it does and how it works; I'm not asking
    > for programming help. I'm posing it as a puzzle for amusement and
    > edification.
    >
    > Background:
    >
    > It's a C implementation of an algorithm I found in a rather famous
    > book, for a rather simple and important arithmetic problem (which
    > shows up as a subproblem in Gray codes, low-discrepancy sequences, and
    > many other problems), and is one of the fastest and most compact
    > solutions to this problem that I could find (without using assembly)
    > (although there is one slightly faster method on my machine that is
    > not so compact).
    >
    > What I found amusing is that, if you don't comment the code, it seems
    > quite nonobvious what this algorithm computes, and even if you deduce
    > that from the function outputs it seems very nonobvious why/how it
    > works.
    >
    > Regards,
    > Steven G. Johnson
    >
     
    Gerry Ford, Mar 10, 2008
    #11
  12. Steven G. Johnson

    user923005 Guest

    On Mar 9, 10:40 am, "Steven G. Johnson" <> wrote:
    > Here is a little algorithm I came across whose implementation is
    > amusingly obscure: what simple function does the following C code
    > compute, and why?
    >
    > #include <stdint.h>
    > unsigned foo(uint32_t n)
    > {
    >      const uint32_t a = 0x05f66a47;
    >      static const unsigned bar[32] =
    > {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,­10,29,9,8,7};
    >      n = ~n;
    >      return bar[(a * (n & (-n))) >> 27];
    >
    > }
    >
    > To save you the trouble of compiling and running it yourself, here is
    > what it produces for n = 0,1,2,...,31:
    >
    > 0 -> 0, 1 -> 1, 2 -> 0, 3 -> 2, 4 -> 0, 5 -> 1, 6 -> 0, 7 -> 3, 8 ->
    > 0, 9 -> 1, 10 -> 0, 11 -> 2, 12 -> 0, 13 -> 1, 14 -> 0, 15 -> 4, 16 ->
    > 0, 17 -> 1, 18 -> 0, 19 -> 2, 20 -> 0, 21 -> 1, 22 -> 0, 23 -> 3, 24 -
    >
    >
    >
    > > 0, 25 -> 1, 26 -> 0, 27 -> 2, 28 -> 0, 29 -> 1, 30 -> 0, 31 -> 5- Hide quoted text -


    Here's a 64 bit version of something very similar:
    const int lsz64_tbl[64] =
    {
    0, 31, 4, 33, 60, 15, 12, 34,
    61, 25, 51, 10, 56, 20, 22, 35,
    62, 30, 3, 54, 52, 24, 42, 19,
    57, 29, 2, 44, 47, 28, 1, 36,
    63, 32, 59, 5, 6, 50, 55, 7,
    16, 53, 13, 41, 8, 43, 46, 17,
    26, 58, 49, 14, 11, 40, 9, 45,
    21, 48, 39, 23, 18, 38, 37, 27,
    };
    //Gerd Isenberg's implementation of bitscan:
    int GerdBitScan(Bitboard bb)
    {
    const Bitboard lsb = (bb & -(long long) bb) - 1;
    const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
    return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
    }

    //Gerd Isenberg's implementation of bitscan with clear:
    int GerdBitScanReset(Bitboard *bb)
    {
    const Bitboard lsb = (bb[0] & -(long long) bb[0]) - 1;
    const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
    bb[0] &= (bb[0] - 1);
    return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
    }

    Chess programmers will recognize DeBrun's sequences. It was
    popularized by Matthew Henry, IIRC.
    See, for instance:
    http://chessprogramming.wikispaces.com/BitScan
     
    user923005, Mar 10, 2008
    #12
  13. Steven G. Johnson

    user923005 Guest

    On Mar 10, 3:02 pm, user923005 <> wrote:
    > On Mar 9, 10:40 am, "Steven G. Johnson" <> wrote:
    >
    >
    >
    >
    >
    > > Here is a little algorithm I came across whose implementation is
    > > amusingly obscure: what simple function does the following C code
    > > compute, and why?

    >
    > > #include <stdint.h>
    > > unsigned foo(uint32_t n)
    > > {
    > >      const uint32_t a = 0x05f66a47;
    > >      static const unsigned bar[32] =
    > > {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,­­10,29,9,8,7};
    > >      n = ~n;
    > >      return bar[(a * (n & (-n))) >> 27];

    >
    > > }

    >
    > > To save you the trouble of compiling and running it yourself, here is
    > > what it produces for n = 0,1,2,...,31:

    >
    > > 0 -> 0, 1 -> 1, 2 -> 0, 3 -> 2, 4 -> 0, 5 -> 1, 6 -> 0, 7 -> 3, 8 ->
    > > 0, 9 -> 1, 10 -> 0, 11 -> 2, 12 -> 0, 13 -> 1, 14 -> 0, 15 -> 4, 16 ->
    > > 0, 17 -> 1, 18 -> 0, 19 -> 2, 20 -> 0, 21 -> 1, 22 -> 0, 23 -> 3, 24 -

    >
    > > > 0, 25 -> 1, 26 -> 0, 27 -> 2, 28 -> 0, 29 -> 1, 30 -> 0, 31 -> 5- Hide quoted text -

    >
    > Here's a 64 bit version of something very similar:
    > const int       lsz64_tbl[64] =
    > {
    >     0, 31, 4, 33, 60, 15, 12, 34,
    >     61, 25, 51, 10, 56, 20, 22, 35,
    >     62, 30, 3, 54, 52, 24, 42, 19,
    >     57, 29, 2, 44, 47, 28, 1, 36,
    >     63, 32, 59, 5, 6, 50, 55, 7,
    >     16, 53, 13, 41, 8, 43, 46, 17,
    >     26, 58, 49, 14, 11, 40, 9, 45,
    >     21, 48, 39, 23, 18, 38, 37, 27,};
    >
    > //Gerd Isenberg's implementation of bitscan:
    > int             GerdBitScan(Bitboard bb)
    > {
    >     const Bitboard  lsb = (bb & -(long long) bb) - 1;
    >     const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
    >     return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
    >
    > }
    >
    > //Gerd Isenberg's implementation of bitscan with clear:
    > int             GerdBitScanReset(Bitboard *bb)
    > {
    >     const Bitboard  lsb = (bb[0] & -(long long) bb[0]) - 1;
    >     const unsigned int foldedLSB = ((int) lsb) ^ ((int) (lsb >> 32));
    >     bb[0] &= (bb[0] - 1);
    >     return lsz64_tbl[foldedLSB * 0x78291ACF >> 26];
    >
    > }
    >
    > Chess programmers will recognize DeBrun's sequences.  It was
    > popularized by Matthew Henry, IIRC.
    > See, for instance:http://chessprogramming.wikispaces.com/BitScan- Hide quoted text -
    >
    > - Show quoted text -


    Oops... Left out the typedef necessary to grok this code:
    typedef unsigned long long Bitboard;
     
    user923005, Mar 10, 2008
    #13
  14. Steven G. Johnson

    Richard Guest

    CBFalconer <> writes:

    > "Steven G. Johnson" wrote:
    >>
    >> Here is a little algorithm I came across whose implementation is
    >> amusingly obscure: what simple function does the following C code
    >> compute, and why?
    >>
    >> #include <stdint.h>
    >> unsigned foo(uint32_t n)
    >> {
    >> const uint32_t a = 0x05f66a47;
    >> static const unsigned bar[32] =
    >> {0,1,2,26,23,3,15,27,24,21,19,4,12,16,28,6,31,25,22,14,20,18,11,5,30,13,17,10,29,9,8,7};
    >> n = ~n;
    >> return bar[(a * (n & (-n))) >> 27];
    >> }

    >
    > Doesn't seem to work very well on a machine with 16 bit integers.
    >
    > --
    > [mail]: Chuck F (cbfalconer at maineline dot net)
    > [page]: <http://cbfalconer.home.att.net>
    > Try the download section.


    Why? Please explain.
     
    Richard, Mar 10, 2008
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    1,802
    Timothy Bendfelt
    Jan 19, 2007
  2. 64-bit puzzle

    , Feb 3, 2007, in forum: C++
    Replies:
    7
    Views:
    449
  3. Replies:
    9
    Views:
    1,011
    Juha Nieminen
    Aug 22, 2007
  4. Rick Dearman

    A bit of fun. A programming puzzle to be done in C.

    Rick Dearman, Jan 3, 2009, in forum: C Programming
    Replies:
    17
    Views:
    590
  5. Jeff.M
    Replies:
    6
    Views:
    186
    Lasse Reichstein Nielsen
    May 4, 2009
Loading...

Share This Page