Velocity Reviews > a bit of a puzzle

# a bit of a puzzle

Gerry Ford
Guest
Posts: n/a

 03-10-2008
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" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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
>

user923005
Guest
Posts: n/a

 03-10-2008
On Mar 9, 10:40*am, "Steven G. Johnson" <(E-Mail Removed)> 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,2 2,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
Guest
Posts: n/a

 03-10-2008
On Mar 10, 3:02*pm, user923005 <(E-Mail Removed)> wrote:
> On Mar 9, 10:40*am, "Steven G. Johnson" <(E-Mail Removed)> 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,2 2,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;

Richard
Guest
Posts: n/a

 03-10-2008
CBFalconer <(E-Mail Removed)> 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,2 2,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>