Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

a bit of a puzzle

 
 
Steven G. Johnson
Guest
Posts: n/a
 
      03-09-2008
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

 
Reply With Quote
 
 
 
 
Richard Heathfield
Guest
Posts: n/a
 
      03-09-2008
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
 
Reply With Quote
 
 
 
 
Steven G. Johnson
Guest
Posts: n/a
 
      03-09-2008
On Mar 9, 1:58 pm, Richard Heathfield <(E-Mail Removed)> 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?
 
Reply With Quote
 
Harald van Dijk
Guest
Posts: n/a
 
      03-09-2008
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,2 2,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.
 
Reply With Quote
 
Steven G. Johnson
Guest
Posts: n/a
 
      03-09-2008
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
 
CBFalconer
Guest
Posts: n/a
 
      03-10-2008
"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.



--
Posted via a free Usenet account from http://www.teranews.com

 
Reply With Quote
 
Steven G. Johnson
Guest
Posts: n/a
 
      03-10-2008
On Mar 9, 2:31 pm, Harald van Dk <(E-Mail Removed)> 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
 
Reply With Quote
 
Keith Thompson
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.


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) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      03-10-2008
Keith Thompson wrote:
> 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.

>
> 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

 
Reply With Quote
 
Joachim Schmitz
Guest
Posts: n/a
 
      03-10-2008
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,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.

Mind to enlighten me why?

Bye, Jojo



 
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