Shorten this popcount and tesbed

Francois Grieu

unread,

Jan 17, 2010, 12:36:09 PM1/17/10

to

/*
Two independent puzzles about the present C program, which
compiles and produce OK when run (in a hosted environment).

1) Shorten as much as possible the line following the comment,
keeping the rest of the program unmodified, so that it still
produce OK.

2) Make the program as short as possible (ignoring spaces and
end-of-line), without changing what happens when the line
following the comment is changed.

Francois Grieu
*/
#define
P(n)(((n)&1)+5-!((n)&2)-!((n)&4)-!((n)&8)-!((n)&16)-!((n)&32)+((n)>>6)-((n)>>7))

#include <stdio.h>
int main(void)
{
int j;
for( j = 255; j -= !(P(0?0:j&(j-1))+1+(-P(j))); );
puts("OK");
return 0;
#if !P(0)
}
#endif

sfuerst

unread,

Jan 17, 2010, 2:28:17 PM1/17/10

to

1. Courtesy of Bruce Dawson via the Bit Twiddling Hacks website:

#define P(n)(((n)*35185445863425&76861433640456465)%15)

2. I can't quite understand what you mean here. The following loop is
the same as yours, but a bit smaller in characters.

for( j = 255; j -= P(j)==1+P(j&(j-1)); );

Steven

Francois Grieu

unread,

Jan 17, 2010, 3:33:41 PM1/17/10

to

sfuerst a �crit :

> On Jan 17, 9:36 am, Francois Grieu <fgr...@gmail.com> wrote:
>> /*
>> Two independent puzzles about the present C program, which
>> compiles and produce OK when run (in a hosted environment).
>>
>> 1) Shorten as much as possible the line following the comment,
>> keeping the rest of the program unmodified, so that it still
>> produce OK.
>>
>> 2) Make the program as short as possible (ignoring spaces and
>> end-of-line), without changing what happens when the line
>> following the comment is changed.
>>
>> Francois Grieu
>> */
>> #define
>> P(n)(((n)&1)+5-!((n)&2)-!((n)&4)-!((n)&8)-!((n)&16)-!((n)&32)+((n)>>6)-((n)>>7))
>>
>> #include <stdio.h>
>> int main(void)
>> {
>> int j;
>> for( j = 255; j -= !(P(0?0:j&(j-1))+1+(-P(j))); );
>> puts("OK");
>> return 0;
>> #if !P(0)
>> }
>> #endif
>
> 1. Courtesy of Bruce Dawson via the Bit Twiddling Hacks website:
>
> #define P(n)(((n)*35185445863425&76861433640456465)%15)

Nice, but requires 58-bit arithmetic. Many C89 compilers do not.

Thank for the fascinating references!
http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64
<offtopic>
http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item169
</offtopic>

> 2. I can't quite understand what you mean here. The following loop is
> the same as yours, but a bit smaller in characters.
>
> for( j = 255; j -= P(j)==1+P(j&(j-1)); );

Your program's output differ from the original's if the line after
the comment is changed to
#define P(n)((n*35185445863425&76861433640456465)%15)
or to
#define P(n)1==0
which the original rejects for obvious reasons.

Francois Grieu

unread,

Jan 17, 2010, 5:23:15 PM1/17/10

to

/*
Two independent puzzles about the present C89 program, which

compiles and produce OK when run (in a hosted environment).

1) Shorten as much as possible the line following the comment,

keeping the rest of the program unmodified, and the same output.

2) Make the program as short as possible (ignoring spaces and
end-of-line), without changing what happens when the line
following the comment is changed.

Francois Grieu (reposted with refinements)
*/
#define P(n)((((n)&31)*1057&4681)%7+(((n)>>5)*9&53)%5)

#include <stdio.h>
int main(void)
{
int j;

for( j = 255; j -= !((P(0?0:j-1&j))+1+(-P(j))); );

sfuerst

unread,

Jan 17, 2010, 7:13:45 PM1/17/10

to

How about:

#define P(n)(((n)&73)%7+((n)/2&73)%7+((n)/4&9)%7)

Steven

Francois Grieu

unread,

Jan 18, 2010, 1:41:06 AM1/18/10

to

sfuerst wrote :
> How about:
>
> #define P(n)(((n)&73)%7+((n)/2&73)%7+((n)/4&9)%7)

dense

sfuerst

unread,

Jan 18, 2010, 3:04:15 AM1/18/10

to

And this is even shorter:

#define P(n)(((n)*0x8040201UL&~0/15UL)%15)

Steven

Francois Grieu

unread,

Jan 18, 2010, 4:42:16 AM1/18/10

to

sfuerst wrote :

Close, but at runtime, C89 allows ~0 to be two to the power n
minus one for any integer n at least 15; n is 16 on several of
my target platforms.
And even though n is 32 where I compile now, P(32) gives 0.

Francois Grieu

unread,

Jan 18, 2010, 5:52:23 AM1/18/10

to

sfuerst wrote :

Close, but at runtime, C89 allows ~0 to be two to the power n
minus one for any integer n at least 16; n is 16 on several of

my target platforms.
And even though n is 32 where I compile now, P(32) gives 0.

Francois Grieu [reposted with correction]

sfuerst

unread,

Jan 18, 2010, 4:24:23 PM1/18/10

to

Yeah, the above only works with 64bit longs. Hopefully the following
will work better on 32bit machines:

#define P(n)(((n)*134480385u/8&~0ul/15)%15)

Steven

Francois Grieu

unread,

Jan 18, 2010, 4:26:40 PM1/18/10

to

sfuerst wrote :

I can trade %7 for () but that's neutral on size

#define P(n)((((n)/4&9)+((n)/2&73))%7+((n)&73)%7)

Francois Grieu

Dann Corbit

unread,

Jan 18, 2010, 4:47:13 PM1/18/10

to

In article <4b534a8a$0$17819$426a...@news.free.fr>, fgr...@gmail.com
says...

Francois Grieu

unread,

Jan 19, 2010, 2:17:37 AM1/19/10

to

sfuerst wrote :

~0ul/15 assumes that unsigned long is n*4 bits. Also, an
unsigned int of 29 bits is OK by chapter and verse.

On the other hand, there is
#define P(n)(((n)*134480385UL/8&286331153)%15))
but it breaks no character size record. And I remember some
preprocessor that did not understand UL.

Francois Grieu

sfuerst

unread,

Jan 19, 2010, 2:59:28 AM1/19/10

to

<snip>

> > Yeah, the above only works with 64bit longs. Hopefully the following
> > will work better on 32bit machines:
>
> > #define P(n)(((n)*134480385u/8&~0ul/15)%15)
>
> ~0ul/15 assumes that unsigned long is n*4 bits. Also, an
> unsigned int of 29 bits is OK by chapter and verse.
>
> On the other hand, there is
> #define P(n)(((n)*134480385UL/8&286331153)%15))
> but it breaks no character size record. And I remember some
> preprocessor that did not understand UL.
>
> Francois Grieu

To be ansi C, ULONG_MAX must be at least 4294967295, and thus have
enough dynamic range for ~0ul/15 to work for its intended purpose. :-)

You are right though, a perverse implementation with unsigned ints 29
bits long will cause the above to fail. In which case, you need to
spend an extra character to convert 134480385u into 134480385ul.
However, realistically speaking no such implementation exists, so I
wouldn't bother for real-world code. (Even machines with 9bit chars
end up with unsigned ints of 18bits, which will nicely promote to
36bit unsigned longs.)

Also, if the preprocessor doesn't understand the "ul" suffix, then you
aren't talking about C, but some other language. Remember, that an
undefined non-C compiler could do absolutely anything with valid C
code, so there isn't much point discussing hypotheticals unless you
have a particular implementation in mind. If so, discussing its
limitations, and the work-arounds required could be interesting, but
perhaps would be off-topic for this newsgroup.

Steven

Francois Grieu

unread,

Jan 19, 2010, 3:12:32 AM1/19/10

to

sfuerst wrote :

> <snip>
>
>>> Yeah, the above only works with 64bit longs. Hopefully the following
>>> will work better on 32bit machines:
>>> #define P(n)(((n)*134480385u/8&~0ul/15)%15)
>> ~0ul/15 assumes that unsigned long is n*4 bits. Also, an
>> unsigned int of 29 bits is OK by chapter and verse.
>>
>> On the other hand, there is
>> #define P(n)(((n)*134480385UL/8&286331153)%15))
>> but it breaks no character size record. And I remember some
>> preprocessor that did not understand UL.
>>
>> Francois Grieu
>
> To be ansi C, ULONG_MAX must be at least 4294967295, and thus have
> enough dynamic range for ~0ul/15 to work for its intended purpose. :-)

No. If ULONGMAX is 0x1FFFFFFFF, ~0ul/15 is 0x22222222 and the whole
thing falls apart.

> You are right though, a perverse implementation with unsigned ints 29
> bits long will cause the above to fail. In which case, you need to
> spend an extra character to convert 134480385u into 134480385ul.
> However, realistically speaking no such implementation exists, so I
> wouldn't bother for real-world code. (Even machines with 9bit chars
> end up with unsigned ints of 18bits, which will nicely promote to
> 36bit unsigned longs.)

I think I can remember some (ICL?) where a wide integer type,
similar to today's (unsigned) long in C, was implemented using
the floating point coprocessor and masking the result to some
weird number of bits.

> Also, if the preprocessor doesn't understand the "ul" suffix, then you
> aren't talking about C, but some other language. Remember, that an
> undefined non-C compiler could do absolutely anything with valid C
> code, so there isn't much point discussing hypotheticals unless you
> have a particular implementation in mind. If so, discussing its
> limitations, and the work-arounds required could be interesting, but
> perhaps would be off-topic for this newsgroup.

Right.

> Steven

Francois Grieu

unread,

Jan 19, 2010, 7:33:47 AM1/19/10

to

I wrote :

> I think I can remember some (ICL?) where a wide integer type,
> similar to today's (unsigned) long in C, was implemented using
> the floating point coprocessor and masking the result to some
> weird number of bits.

Further, on more modern hardware: industry-standard IEEE-754
has double (resp. float) with 52+1 (resp. 23+1) bits of mantissa.

Thus, on an hypothetical CPU/DSP with fast IEEE-754 or similar FP
hardware, and an otherwise limited instruction set, it could make
sense to implement (unsigned) long using double, making it 52 or
53 bit. And it may even make some sense to implement (unsigned) int
using float, making int 23 or 24 bit.

Thus the number of bits in either (unsigned) long or int could
reasonably be odd. Not that I use such a beast, though.

I wish I knew a semi-exhaustive compilation of C type sizes
on real hardware & compilers.

Francois Grieu