Shorten this popcount and tesbed

Discussion in 'C Programming' started by Francois Grieu, Jan 17, 2010.

  1. /*
    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
    Francois Grieu, Jan 17, 2010
    #1
    1. Advertising

  2. Francois Grieu

    sfuerst Guest

    On Jan 17, 9:36 am, Francois Grieu <> 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)

    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
    sfuerst, Jan 17, 2010
    #2
    1. Advertising

  3. sfuerst a écrit :
    > On Jan 17, 9:36 am, Francois Grieu <> 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
    Francois Grieu, Jan 17, 2010
    #3
  4. /*
    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
    Francois Grieu, Jan 17, 2010
    #4
  5. Francois Grieu

    sfuerst Guest

    On Jan 17, 2:23 pm, Francois Grieu <> wrote:
    > /*
    > 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
    sfuerst, Jan 18, 2010
    #5
  6. sfuerst wrote :
    > How about:
    >
    > #define P(n)(((n)&73)%7+((n)/2&73)%7+((n)/4&9)%7)


    dense
    Francois Grieu, Jan 18, 2010
    #6
  7. Francois Grieu

    sfuerst Guest

    On Jan 17, 10:41 pm, Francois Grieu <> 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
    sfuerst, Jan 18, 2010
    #7
  8. sfuerst wrote :
    > On Jan 17, 10:41 pm, Francois Grieu <> 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)


    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
    Francois Grieu, Jan 18, 2010
    #8
  9. sfuerst wrote :
    > On Jan 17, 10:41 pm, Francois Grieu <> 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]
    Francois Grieu, Jan 18, 2010
    #9
  10. Francois Grieu

    sfuerst Guest

    On Jan 18, 2:52 am, Francois Grieu <> wrote:
    > sfuerst wrote :
    >
    > > On Jan 17, 10:41 pm, Francois Grieu <> 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)

    Steven
    sfuerst, Jan 18, 2010
    #10
  11. sfuerst wrote :
    > On Jan 17, 2:23 pm, Francois Grieu <> wrote:
    >> /*
    >> 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)


    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
    Francois Grieu, Jan 18, 2010
    #11
  12. Francois Grieu

    Dann Corbit Guest

    In article <4b534a8a$0$17819$>,
    says...
    >
    > /*
    > 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
    Dann Corbit, Jan 18, 2010
    #12
  13. sfuerst wrote :
    > On Jan 18, 2:52 am, Francois Grieu <> wrote:
    >> sfuerst wrote :
    >>
    >>> On Jan 17, 10:41 pm, Francois Grieu <> 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
    Francois Grieu, Jan 19, 2010
    #13
  14. Francois Grieu

    sfuerst Guest

    <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
    sfuerst, Jan 19, 2010
    #14
  15. 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
    Francois Grieu, Jan 19, 2010
    #15
  16. 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
    Francois Grieu, Jan 19, 2010
    #16
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kenneth Keeley

    Shorten a SQL VarChar result.

    Kenneth Keeley, Oct 28, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    670
    Scott Mitchell [MVP]
    Oct 28, 2004
  2. =?Utf-8?B?V2ViIFJlc3BvbnNlIFRpbWU=?=

    How can I shorten this time?

    =?Utf-8?B?V2ViIFJlc3BvbnNlIFRpbWU=?=, Oct 28, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    324
    Scott Allen
    Oct 28, 2004
  3. Crispy
    Replies:
    3
    Views:
    658
    sinclar sodersas
    Jul 12, 2003
  4. Benjamin Rutt

    finding redundant #includes to shorten compile time

    Benjamin Rutt, Feb 5, 2004, in forum: C Programming
    Replies:
    15
    Views:
    996
    CBFalconer
    Feb 6, 2004
  5. ben
    Replies:
    8
    Views:
    380
Loading...

Share This Page