a bit of a puzzle

[Steven G. Johnson]

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

[CBFalconer]

Re: a bit of a puzzle

"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

[Keith Thompson]

Re: a bit of a puzzle

CBFalconer <cbfalconer@yah oo.comwrites:

"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,3 1,25,22,14,20,1 8,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_Keit h) <kst-u@mib.org>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Joachim Schmitz]

Re: a bit of a puzzle

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,3 1,25,22,14,20,1 8,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

[user923005]

Re: a bit of a puzzle

On Mar 9, 10:40 am, "Steven G. Johnson" <stev...@alum.m it.eduwrote:

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(Bit board 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 GerdBitScanRese t(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]

Re: a bit of a puzzle

On Mar 10, 3:02 pm, user923005 <dcor...@connx. comwrote:

On Mar 9, 10:40 am, "Steven G. Johnson" <stev...@alum.m it.eduwrote:
>
>
>
>
>

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- Hidequoted 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(Bit board 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             GerdBitScanRese t(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]

Re: a bit of a puzzle

CBFalconer <cbfalconer@yah oo.comwrites:

"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,3 1,25,22,14,20,1 8,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.

[CBFalconer]

Re: a bit of a puzzle

Keith Thompson wrote:

CBFalconer <cbfalconer@yah oo.comwrites:

>"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,1 9,4,12,16,28,6, 31,25,22,14,20, 18,11,5,30,13,1 7,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