Shorten this popcount and tesbed

F

Francois Grieu

/*
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
 
S

sfuerst

/*
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)

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
 
F

Francois Grieu

sfuerst a écrit :
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
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
 
F

Francois Grieu

/*
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))); );
puts("OK");
return 0;
#if !P(0)
}
#endif
 
S

sfuerst

/*
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))); );
     puts("OK");
     return 0;
#if !P(0)
     }
#endif


How about:

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

Steven
 
F

Francois Grieu

sfuerst wrote :
And this is even shorter:

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

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
 
F

Francois Grieu

sfuerst wrote :
And this is even shorter:

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

Steven

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

sfuerst

sfuerst wrote :
And this is even shorter:
#define P(n)(((n)*0x8040201UL&~0/15UL)%15)

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]

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
 
F

Francois Grieu

sfuerst wrote :
How about:

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

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
 
D

Dann Corbit

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

Tangentially related:
http://chessprogramming.wikispaces.com/Population+Count
 
F

Francois Grieu

sfuerst wrote :
sfuerst wrote :
sfuerst wrote :
How about:
#define P(n)(((n)&73)%7+((n)/2&73)%7+((n)/4&9)%7)
dense
And this is even shorter:
#define P(n)(((n)*0x8040201UL&~0/15UL)%15)
Steven
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]

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
 
S

sfuerst

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

Francois Grieu

sfuerst wrote :
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
 
F

Francois Grieu

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top