Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > a bit of a puzzle

Reply
Thread Tools

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
>



 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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;

 
Reply With Quote
 
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>
> Try the download section.


Why? Please explain.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the point of having 16 bit colour if a computer monitor can only display 8 bit colour? How do you edit 16 bit colour when you can only see 8 bit? Scotius Digital Photography 6 07-13-2010 03:33 AM
64-bit puzzle karpov2007@gmail.com C++ 7 02-06-2007 05:00 PM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit, Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new ! vvcd Computer Support 0 09-17-2004 08:15 PM
A puzzle to puzzle you sk A+ Certification 1 07-17-2004 05:19 PM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit,Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new! Ionizer Computer Support 1 01-01-2004 07:27 PM



Advertisments