www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Programing Puzzles

reply Wyverex <wyverex.cypher gmail.com> writes:
just some fun little programming puzzles I found around online...



Write a "Hello World" program in 'C' without using a semicolon.
(Note: #include in C doesn't need a semicolon but import does)




import statement.


(Cant use: do, while, for, foreach, if).


to print numbers from 1 to 100 and 100 to 1;





Post Solutions to this root, comments to someones solution in that thread.
Aug 06 2008
next sibling parent reply Wyverex <wyverex.cypher gmail.com> writes:
Wyverex wrote:

 just some fun little programming puzzles I found around online...
 
 
 
 Write a "Hello World" program in 'C' without using a semicolon.
 (Note: #include in C doesn't need a semicolon but import does)
 
 
 

 import statement.
 

 (Cant use: do, while, for, foreach, if).
 

 to print numbers from 1 to 100 and 100 to 1;
 

 
 
 
 Post Solutions to this root, comments to someones solution in that thread.


Solutions, Don't Peek if you havn't tried them yet!



import tango.io.Stdout;

void main()
{
   if(Stdout("Hello World")) {}
}



import tango.io.Stdout;

void main()
{
   int x = 2;

   char[][2] ans = ["Even", "Odd"];
   Stdout( ans[ x & 1 ] ).newline;
}


import tango.io.Stdout;

void countUP( int i )()
{
   Stdout(i)(" ");
   countUP!(i+1);
}

void countUP( int i : 101 )() {}

void countDN( int i )()
{
   Stdout(i)(" ");
   countDN!(i-1);
}

void countDN( int i : 0 )() {}

void main()
{
   countUP!(1);
   Stdout.newline;
   countDN!(100);
}


import tango.io.Stdout;

bool test( in uint i )
{
   int c = 0;
   while( i > 0 )
   {
     c += i & 1;
     i = i >> 1;
   }
   return ( c == 1? true : false );
}

void main()
{
    for(uint x = 0; x < uint.max ; ++x)
       if(test(x)) Stdout(x).newline;
}
Aug 06 2008
parent reply Lutger <lutger.blijdestijn gmail.com> writes:
Wyverex wrote:
 


 import tango.io.Stdout;
 
 void main()
 {
    if(Stdout("Hello World")) {}
 }


this works, no semicolon needed with phobos:

void main()
{
    if( printf("Hello World"), true )
    {
    }
}
Aug 06 2008
parent reply Wyverex <wyverex.cypher gmail.com> writes:
Sweet! Didn't know printf was accessible without an import!
10pts!

Lutger wrote:

 Wyverex wrote:
  


 import tango.io.Stdout;

 void main()
 {
    if(Stdout("Hello World")) {}
 }


 
 this works, no semicolon needed with phobos:
 
 void main()
 {
     if( printf("Hello World"), true )
     {
     }
 }
Aug 06 2008
parent Lars Ivar Igesund <larsivar igesund.net> writes:
Wyverex wrote:


 Sweet! Didn't know printf was accessible without an import!
 10pts!


Actually this is due to a bad decision early on, where printf was put into
object.d. It is not part of Tango's object.

-- 
Lars Ivar Igesund
blog at http://larsivi.net
DSource, #d.tango & #D: larsivi
Dancing the Tango
Aug 07 2008
prev sibling next sibling parent BCS <ao pathlink.com> writes:
Reply to wyverex,


 just some fun little programming puzzles I found around online...
 

 statement (Cant use: do, while, for, foreach, if).


bool isEven(int i) {return !(i & 0x01);}


 

 to print numbers from 1 to 100 and 100 to 1;


void DoIt(int i = 1)
{
    writef("%d\n", i);
    i==100 || DoIt(i+1);
    writef("%d\n", i);
}


 

 


bool isPow(int i)
{
  if(!i) return true;
  while(!(i & 0x01)) i>>=1;
  return !(i ^ 0x01);
}
Aug 06 2008
prev sibling next sibling parent reply Wyverex <wyverex.cypher gmail.com> writes:
Through another one in....



(Multiply x by 7 without using multiplication (*) operator.)

Bonus Problem!
Multiply X by Y without using multiplication (*) operator..  Faster the 
better!!!
Aug 06 2008
next sibling parent Wyverex <wyverex.cypher gmail.com> writes:
Wyverex wrote:

 Through another one in....
 
 
 
 (Multiply x by 7 without using multiplication (*) operator.)
 
 Bonus Problem!
 Multiply X by Y without using multiplication (*) operator..  Faster the 
 better!!!



import tango.io.Stdout;

uint mult ( in uint a, in uint b )
{
    uint shift, ans;

    while( b )
    {
       ans += ( b & 1 ? a << shift : 0 );
       shift ++;
       b >>= 1;
    }
    return ans;
}

void main()
{
   uint x = 92;
   uint y = 478;

   Stdout( x * y ).newline;  //here to prove value is right!!
   Stdout( mult(x, y) ).newline;
}
Aug 06 2008
prev sibling parent BCS <ao pathlink.com> writes:
Reply to wyverex,


 Through another one in....
 
 (Multiply x by 7 without using multiplication (*) operator.)
 
 Bonus Problem!
 Multiply X by Y without using multiplication (*) operator..  Faster
 the
 better!!!


int Mul(int i, int j)
{
   int ret = 0;
   while(j)
   {
      if(j & 0x01) ret += i;
      j >>= 1;
      i <<= 1;
   }
   return ret;
}


now do div :)
Aug 06 2008
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
char a=0,b=0,c=0,d=0;
while(a<5 || b<9 || c<5 || d<9)
{
   writef("%d%d:%d%d\n", a,b,c,d);

   // add a single /expression/ here
}

make that count from "00:00" to "59:59" (minutes and seconds)

I seem to remember I figured this out once, but I don't remember how I did it.
Aug 06 2008
parent reply Wyverex <wyverex.cypher gmail.com> writes:
BCS wrote:

 
 char a=0,b=0,c=0,d=0;
 while(a<5 || b<9 || c<5 || d<9)
 {
   writef("%d%d:%d%d\n", a,b,c,d);
 
   // add a single /expression/ here
 }
 
 make that count from "00:00" to "59:59" (minutes and seconds)
 
 I seem to remember I figured this out once, but I don't remember how I 
 did it.
 
 





import std.stdio;

void main()
{


char a=0,b=0,c=0,d=0;

do{
   writef("%d%d:%d%d\n", a,b,c,d);

    ( d == 9 ? d = 0 || (c == 5 ? c = 0 || ( b == 9 ? b = 0 || ++a : ++b 
)  : ++c) : ++d);

}while(a<6 || b<0 || c<0 || d<0)

}
Aug 06 2008
parent BCS <ao pathlink.com> writes:
Reply to wyverex,


 BCS wrote:
 

 char a=0,b=0,c=0,d=0;
 while(a<5 || b<9 || c<5 || d<9)
 {
 writef("%d%d:%d%d\n", a,b,c,d);
 // add a single /expression/ here
 }
 make that count from "00:00" to "59:59" (minutes and seconds)
 
 I seem to remember I figured this out once, but I don't remember how
 I did it.
 


 import std.stdio;
 
 void main()
 {
 char a=0,b=0,c=0,d=0;
 
 do{
 writef("%d%d:%d%d\n", a,b,c,d);
 ( d == 9 ? d = 0 || (c == 5 ? c = 0 || ( b == 9 ? b = 0 || ++a :
 ++b )  : ++c) : ++d);
 
 }while(a<6 || b<0 || c<0 || d<0)
 
 }
 


yah, that looks right. I think I used a comma expression or some sutch.
Aug 06 2008
prev sibling next sibling parent reply "Koroskin Denis" <2korden gmail.com> writes:
On Thu, 07 Aug 2008 01:50:56 +0400, Wyverex <wyverex.cypher gmail.com>  =

wrote:


 just some fun little programming puzzles I found around online...



 Write a "Hello World" program in 'C' without using a semicolon.
 (Note: #include in C doesn't need a semicolon but import does)






  =


 import statement.




nt  =


 (Cant use: do, while, for, foreach, if).




  =


 to print numbers from 1 to 100 and 100 to 1;




// 0 is considered a power of two here
bool isPowerOfTwo(int i) {
	return (i & (i-1) =3D=3D 0);
}
Aug 06 2008
parent reply BCS <ao pathlink.com> writes:
Reply to Koroskin,


 On Thu, 07 Aug 2008 01:50:56 +0400, Wyverex <wyverex.cypher gmail.com>
 wrote:
 

 just some fun little programming puzzles I found around online...
 
 Write a "Hello World" program in 'C' without using a semicolon.
 (Note: #include in C doesn't need a semicolon but import does)
 

 on  import statement.
 

 statement  (Cant use: do, while, for, foreach, if).
 

 etc)  to print numbers from 1 to 100 and 100 to 1;
 

 


 // 0 is considered a power of two here
 bool isPowerOfTwo(int i) {
 return (i & (i-1) == 0);
 }


isPowerOfTwo(int.min);


0b10000000  == byte.min
0b01111111  == byte.min -1

0b00000000
Aug 06 2008
parent reply JAnderson <ask me.com> writes:
BCS wrote:

 Reply to Koroskin,
 

 On Thu, 07 Aug 2008 01:50:56 +0400, Wyverex <wyverex.cypher gmail.com>
 wrote:


 just some fun little programming puzzles I found around online...

 Write a "Hello World" program in 'C' without using a semicolon.
 (Note: #include in C doesn't need a semicolon but import does)


 on  import statement.


 statement  (Cant use: do, while, for, foreach, if).


 etc)  to print numbers from 1 to 100 and 100 to 1;




 // 0 is considered a power of two here
 bool isPowerOfTwo(int i) {
 return (i & (i-1) == 0);
 }


 
 isPowerOfTwo(int.min);
 
 
 0b10000000  == byte.min
 0b01111111  == byte.min -1
 
 0b00000000
 
 




What are you trying to say?  I imagine your validating Koroskin solution.

10000000  == byte.min
01111111  == byte.min - 1
=
00000000  == is power of 2

-Joel
Aug 06 2008
parent reply BCS <ao pathlink.com> writes:
Reply to janderson,



 What are you trying to say?  I imagine your validating Koroskin
 solution.
 
 10000000  == byte.min
 01111111  == byte.min - 1
 =
 00000000  == is power of 2
 -Joel
 


byte.min < 0, all powers of 2 are gratter than zero
Aug 08 2008
parent reply BCS <ao pathlink.com> writes:
Reply to Benjamin,


 Reply to janderson,
 

 What are you trying to say?  I imagine your validating Koroskin
 solution.
 
 10000000  == byte.min
 01111111  == byte.min - 1
 =
 00000000  == is power of 2
 -Joel


 byte.min < 0, all powers of 2 are gratter than zero
 


OTOH my solution fails in the same case :(
Aug 08 2008
parent JAnderson <ask me.com> writes:
BCS wrote:

 Reply to Benjamin,
 

 Reply to janderson,


 What are you trying to say?  I imagine your validating Koroskin
 solution.

 10000000  == byte.min
 01111111  == byte.min - 1
 =
 00000000  == is power of 2
 -Joel


 byte.min < 0, all powers of 2 are gratter than zero


 
 OTOH my solution fails in the same case :(
 
 


ic, I was thinking unsigned byte.  Pretty easy to test for if you need 
to use unsigned numbers in that range.

-Joel
Aug 09 2008
prev sibling next sibling parent reply JAnderson <ask me.com> writes:
Wyverex wrote:

 just some fun little programming puzzles I found around online...
 
 

 (Cant use: do, while, for, foreach, if).
 

 
 Post Solutions to this root, comments to someones solution in that thread.



Some of these are pretty standard interview questions. Although I don't 
personally like to ask these sort of questions because they are often 
about knowing a "trick" which you an easily lookup.  The can be fun to 
figure out though.

Here's another common one:

| Write a bitcount for a 32-bit number.

And a little more challenging:

| Write a bitcount for a 32-bit number that is less then 15 operations 
without using a lookup table.

| Can you do that in 12 or less?

-Joel
Aug 06 2008
parent reply Wyverex <wyverex.cypher gmail.com> writes:
JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I found around online...



 statement (Cant use: do, while, for, foreach, if).



 Post Solutions to this root, comments to someones solution in that 
 thread.


 
 
 Some of these are pretty standard interview questions. Although I don't 
 personally like to ask these sort of questions because they are often 
 about knowing a "trick" which you an easily lookup.  The can be fun to 
 figure out though.
 
 Here's another common one:
 
 | Write a bitcount for a 32-bit number.
 
 And a little more challenging:
 
 | Write a bitcount for a 32-bit number that is less then 15 operations 
 without using a lookup table.
 
 | Can you do that in 12 or less?
 
 -Joel


int count( in int i )
{
    int c = (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
    i >>= 4;
    c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
    i >>= 4;
    c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
    i >>= 4;
    c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);

    return c;
}

int count2( in int i )
{
    int c = (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
    i >>= 4;
    c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
    i >>= 4;
    c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
    i >>= 4;
    c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);

    return c;
}
Aug 07 2008
parent reply "Koroskin Denis" <2korden gmail.com> writes:
On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher gmail.com>  
wrote:


 JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I found around online...



 statement (Cant use: do, while, for, foreach, if).



 Post Solutions to this root, comments to someones solution in that  
 thread.


   Some of these are pretty standard interview questions. Although I  
 don't personally like to ask these sort of questions because they are  
 often about knowing a "trick" which you an easily lookup.  The can be  
 fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is less then 15 operations  
 without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 :  
 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);

     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);

     return c;
 }


Much simpler:

int getBitCount32(int i) {
     return getBitCount16(i) + getBitCount16(i >> 16);
}

int getBitCount16(int i) {
     return getBitCount8(i) + getBitCount8(i >> 8);
}

int getBitCount8(int i) {
     return getBitCount4(i) + getBitCount4(i >> 4);
}

int getBitCount4(int i) {
     return getBitCount2(i) + getBitCount2(i >> 2);
}

int getBitCount2(int i) {
     return (i & 2) + (i & 1);
}
Aug 07 2008
parent reply JAnderson <ask me.com> writes:
Koroskin Denis wrote:

 On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher gmail.com> 
 wrote:
 

 JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I found around online...



 statement (Cant use: do, while, for, foreach, if).



 Post Solutions to this root, comments to someones solution in that 
 thread.


   Some of these are pretty standard interview questions. Although I 
 don't personally like to ask these sort of questions because they are 
 often about knowing a "trick" which you an easily lookup.  The can be 
 fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is less then 15 
 operations without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 
 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);

     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);

     return c;
 }


 
 Much simpler:
 
 int getBitCount32(int i) {
     return getBitCount16(i) + getBitCount16(i >> 16);
 }
 
 int getBitCount16(int i) {
     return getBitCount8(i) + getBitCount8(i >> 8);
 }
 
 int getBitCount8(int i) {
     return getBitCount4(i) + getBitCount4(i >> 4);
 }
 
 int getBitCount4(int i) {
     return getBitCount2(i) + getBitCount2(i >> 2);
 }
 
 int getBitCount2(int i) {
     return (i & 2) + (i & 1);
 }


That's an ok solution although a little complecated for question 1.  It 
can certainly be be done much easier then that.  The classic solution is:

uint v;
uint c;
for (c = 0; v; c++)
{
   v &= v - 1;
}

Which will only loop the number of bits.  However that's not 15ops or 12op.

-Joel
Aug 07 2008
parent reply "Koroskin Denis" <2korden gmail.com> writes:
On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask me.com> wrote:


 Koroskin Denis wrote:

 On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher gmail.com>  
 wrote:


 JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I found around online...



 statement (Cant use: do, while, for, foreach, if).



 Post Solutions to this root, comments to someones solution in that  
 thread.


   Some of these are pretty standard interview questions. Although I  
 don't personally like to ask these sort of questions because they are  
 often about knowing a "trick" which you an easily lookup.  The can be  
 fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is less then 15  
 operations without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 :  
 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);

     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);

     return c;
 }


  Much simpler:
  int getBitCount32(int i) {
     return getBitCount16(i) + getBitCount16(i >> 16);
 }
  int getBitCount16(int i) {
     return getBitCount8(i) + getBitCount8(i >> 8);
 }
  int getBitCount8(int i) {
     return getBitCount4(i) + getBitCount4(i >> 4);
 }
  int getBitCount4(int i) {
     return getBitCount2(i) + getBitCount2(i >> 2);
 }
  int getBitCount2(int i) {
     return (i & 2) + (i & 1);
 }


 That's an ok solution although a little complecated for question 1.  It  
 can certainly be be done much easier then that.  The classic solution is:

 uint v;
 uint c;
 for (c = 0; v; c++)
 {
    v &= v - 1;
 }

 Which will only loop the number of bits.  However that's not 15ops or  
 12op.

 -Joel


Ah, I know where you got it from :) Scroll down, there is also a solution  
for 15 and 12 operations.
Aug 08 2008
parent reply JAnderson <ask me.com> writes:
Koroskin Denis wrote:

 On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask me.com> wrote:
 

 Koroskin Denis wrote:

 On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex 
 <wyverex.cypher gmail.com> wrote:


 JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I found around online...



 statement (Cant use: do, while, for, foreach, if).



 Post Solutions to this root, comments to someones solution in that 
 thread.


   Some of these are pretty standard interview questions. Although I 
 don't personally like to ask these sort of questions because they 
 are often about knowing a "trick" which you an easily lookup.  The 
 can be fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is less then 15 
 operations without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 
 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 : 0);

     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);

     return c;
 }


  Much simpler:
  int getBitCount32(int i) {
     return getBitCount16(i) + getBitCount16(i >> 16);
 }
  int getBitCount16(int i) {
     return getBitCount8(i) + getBitCount8(i >> 8);
 }
  int getBitCount8(int i) {
     return getBitCount4(i) + getBitCount4(i >> 4);
 }
  int getBitCount4(int i) {
     return getBitCount2(i) + getBitCount2(i >> 2);
 }
  int getBitCount2(int i) {
     return (i & 2) + (i & 1);
 }


 That's an ok solution although a little complecated for question 1.  
 It can certainly be be done much easier then that.  The classic 
 solution is:

 uint v;
 uint c;
 for (c = 0; v; c++)
 {
    v &= v - 1;
 }

 Which will only loop the number of bits.  However that's not 15ops or 
 12op.

 -Joel


 
 Ah, I know where you got it from :) Scroll down, there is also a 
 solution for 15 and 12 operations.


I know the answer for 15 / 12 ops I was asking the question.  Also what 
website are you talking about because this is not something I learned 
online.

-Joel
Aug 08 2008
parent reply "Koroskin Denis" <2korden gmail.com> writes:
On Fri, 08 Aug 2008 19:35:39 +0400, JAnderson <ask me.com> wrote:


 Koroskin Denis wrote:

 On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask me.com> wrote:


 Koroskin Denis wrote:

 On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex  
 <wyverex.cypher gmail.com> wrote:


 JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I found around online...



 statement (Cant use: do, while, for, foreach, if).



 Post Solutions to this root, comments to someones solution in that  
 thread.


   Some of these are pretty standard interview questions. Although I  
 don't personally like to ask these sort of questions because they  
 are often about knowing a "trick" which you an easily lookup.  The  
 can be fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is less then 15  
 operations without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1  
 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 :  
 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 :  
 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 :  
 0);

     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) &  
 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);

     return c;
 }


  Much simpler:
  int getBitCount32(int i) {
     return getBitCount16(i) + getBitCount16(i >> 16);
 }
  int getBitCount16(int i) {
     return getBitCount8(i) + getBitCount8(i >> 8);
 }
  int getBitCount8(int i) {
     return getBitCount4(i) + getBitCount4(i >> 4);
 }
  int getBitCount4(int i) {
     return getBitCount2(i) + getBitCount2(i >> 2);
 }
  int getBitCount2(int i) {
     return (i & 2) + (i & 1);
 }


 That's an ok solution although a little complecated for question 1.   
 It can certainly be be done much easier then that.  The classic  
 solution is:

 uint v;
 uint c;
 for (c = 0; v; c++)
 {
    v &= v - 1;
 }

 Which will only loop the number of bits.  However that's not 15ops or  
 12op.

 -Joel


  Ah, I know where you got it from :) Scroll down, there is also a  
 solution for 15 and 12 operations.


 I know the answer for 15 / 12 ops I was asking the question.  Also what  
 website are you talking about because this is not something I learned  
 online.

 -Joel


It looks like a copy-paste from bithacks  
(http://graphics.stanford.edu/~seander/bithacks.html) - a must read for  
everyone!
Aug 08 2008
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Koroskin Denis:

 It looks like a copy-paste from bithacks  
 (http://graphics.stanford.edu/~seander/bithacks.html) - a must read for  
 everyone!


My libs (math module) already contain some translations to D of those "hacks",
including this one.

That page is good, and things will be better as soon as a high enough level
language (D?) will allow to use CPU vector instructions like SSE and the
following ones with a simple enough syntax, we'll probably see 1024 bit ones in
2-4 years:
http://en.wikipedia.org/wiki/Advanced_Vector_Extensions
With 1024 bits you can do *lot* of bitwise computations in one/few clock
tick(s) :-)
There are many algorithms (like building state machines for exact/approximate
string matching) that can become much faster with a portable support of such
CPU instructions (you can use SSE3 with GCC in C but the syntax is hairy and
not standard).

Bye,
bearophile
Aug 08 2008
prev sibling next sibling parent JAnderson <ask me.com> writes:
Koroskin Denis wrote:

 On Fri, 08 Aug 2008 19:35:39 +0400, JAnderson <ask me.com> wrote:
 

 Koroskin Denis wrote:

 On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask me.com> wrote:


 Koroskin Denis wrote:

 On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex 
 <wyverex.cypher gmail.com> wrote:


 JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I found around online...



 statement (Cant use: do, while, for, foreach, if).



 Post Solutions to this root, comments to someones solution in 
 that thread.


   Some of these are pretty standard interview questions. Although 
 I don't personally like to ask these sort of questions because 
 they are often about knowing a "trick" which you an easily 
 lookup.  The can be fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is less then 15 
 operations without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 
 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 
 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 
 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 
 : 0);

     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) 
 & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);

     return c;
 }


  Much simpler:
  int getBitCount32(int i) {
     return getBitCount16(i) + getBitCount16(i >> 16);
 }
  int getBitCount16(int i) {
     return getBitCount8(i) + getBitCount8(i >> 8);
 }
  int getBitCount8(int i) {
     return getBitCount4(i) + getBitCount4(i >> 4);
 }
  int getBitCount4(int i) {
     return getBitCount2(i) + getBitCount2(i >> 2);
 }
  int getBitCount2(int i) {
     return (i & 2) + (i & 1);
 }


 That's an ok solution although a little complecated for question 1.  
 It can certainly be be done much easier then that.  The classic 
 solution is:

 uint v;
 uint c;
 for (c = 0; v; c++)
 {
    v &= v - 1;
 }

 Which will only loop the number of bits.  However that's not 15ops 
 or 12op.

 -Joel


  Ah, I know where you got it from :) Scroll down, there is also a 
 solution for 15 and 12 operations.


 I know the answer for 15 / 12 ops I was asking the question.  Also 
 what website are you talking about because this is not something I 
 learned online.

 -Joel


 
 It looks like a copy-paste from bithacks 
 (http://graphics.stanford.edu/~seander/bithacks.html) - a must read for 
 everyone!


Actually I have been there before.  The code was from some old project 
of mine,  I just wanted to make sure I got it right (with out having to 
think about it and have someone complain that I forgot a ; or 
something).  However maybe that was originally from bithacks.

-Joel
Aug 09 2008
prev sibling parent Don <nospam nospam.com.au> writes:
Koroskin Denis wrote:

 On Fri, 08 Aug 2008 19:35:39 +0400, JAnderson <ask me.com> wrote:
 

 Koroskin Denis wrote:

 On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask me.com> wrote:


 Koroskin Denis wrote:

 On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex 
 <wyverex.cypher gmail.com> wrote:


 JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I found around online...



 statement (Cant use: do, while, for, foreach, if).



 Post Solutions to this root, comments to someones solution in 
 that thread.


   Some of these are pretty standard interview questions. Although 
 I don't personally like to ask these sort of questions because 
 they are often about knowing a "trick" which you an easily 
 lookup.  The can be fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is less then 15 
 operations without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 
 1 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 
 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 
 : 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i & 4 ? 1 : 0) + (i & 8 ? 1 
 : 0);

     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) 
 & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);
     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i >> 2) & 1) + ((i >> 3) & 1);

     return c;
 }


  Much simpler:
  int getBitCount32(int i) {
     return getBitCount16(i) + getBitCount16(i >> 16);
 }
  int getBitCount16(int i) {
     return getBitCount8(i) + getBitCount8(i >> 8);
 }
  int getBitCount8(int i) {
     return getBitCount4(i) + getBitCount4(i >> 4);
 }
  int getBitCount4(int i) {
     return getBitCount2(i) + getBitCount2(i >> 2);
 }
  int getBitCount2(int i) {
     return (i & 2) + (i & 1);
 }


 That's an ok solution although a little complecated for question 1.  
 It can certainly be be done much easier then that.  The classic 
 solution is:

 uint v;
 uint c;
 for (c = 0; v; c++)
 {
    v &= v - 1;
 }

 Which will only loop the number of bits.  However that's not 15ops 
 or 12op.

 -Joel


  Ah, I know where you got it from :) Scroll down, there is also a 
 solution for 15 and 12 operations.


 I know the answer for 15 / 12 ops I was asking the question.  Also 
 what website are you talking about because this is not something I 
 learned online.

 -Joel


 
 It looks like a copy-paste from bithacks 
 (http://graphics.stanford.edu/~seander/bithacks.html) - a must read for 
 everyone!


My solution is already on that page -- look for my name <g>. 14 ops, if 
you have access to rotation.
1 sub, 4 adds, 3 ands, 3 shifts, 3 rotates.
Aug 14 2008
prev sibling next sibling parent reply "Koroskin Denis" <2korden gmail.com> writes:
On Thu, 07 Aug 2008 10:50:25 +0400, JAnderson <ask me.com> wrote:


 Wyverex wrote:

 just some fun little programming puzzles I found around online...
    Write a "Hello World" program in 'C' without using a semicolon.
 (Note: #include in C doesn't need a semicolon but import does)

 on import statement.

 statement (Cant use: do, while, for, foreach, if).

 to print numbers from 1 to 100 and 100 to 1;

    Post Solutions to this root, comments to someones solution in that  
 thread.


 These are pretty standard interview questions. Although I don't  
 personally like to ask these sort of questions because they are often  
 about knowing a "trick" which you an easily lookup.  The can be fun to  
 figure out though.

 Here's another common one:

 | Write a bitcount for a 32-bit number.

 And a little more challenging:

 | Write a bitcount for a 32-bit number that is less then 15 operations  
 without using a lookup table.

 | Can you do that in 12 or less?

 -Joel


I know the solution for 15 operations, but it is impossible to come up  
with solution quickly. Besides, it requires 64 bit arithmetic support.
Aug 07 2008
parent JAnderson <ask me.com> writes:
Koroskin Denis wrote:

 On Thu, 07 Aug 2008 10:50:25 +0400, JAnderson <ask me.com> wrote:
 

 Wyverex wrote:

 just some fun little programming puzzles I found around online...
    Write a "Hello World" program in 'C' without using a semicolon.
 (Note: #include in C doesn't need a semicolon but import does)

 semicolon on import statement.

 statement (Cant use: do, while, for, foreach, if).

 etc) to print numbers from 1 to 100 and 100 to 1;

    Post Solutions to this root, comments to someones solution in that 
 thread.


 These are pretty standard interview questions. Although I don't 
 personally like to ask these sort of questions because they are often 
 about knowing a "trick" which you an easily lookup.  The can be fun to 
 figure out though.

 Here's another common one:

 | Write a bitcount for a 32-bit number.

 And a little more challenging:

 | Write a bitcount for a 32-bit number that is less then 15 operations 
 without using a lookup table.

 | Can you do that in 12 or less?

 -Joel


 
 I know the solution for 15 operations, but it is impossible to come up 
 with solution quickly. Besides, it requires 64 bit arithmetic support.


The 12 op solution doesn't require 64-bit.  Your right though to come up 
with something quickly for a question like this is extremely difficult 
when its been worked on for years, unless you "know" it.

-Joel
Aug 07 2008
prev sibling parent Era Scarecrow <rtcvb32 yahoo.com> writes:
Koroskin Denis wrote:

 

 JAnderson wrote:

 Wyverex wrote:

 just some fun little programming puzzles I






 found around online...








 without looping or if  

 statement (Cant use: do, while, for, foreach,






 if).








 of 2.

 Post Solutions to this root, comments to






 someones solution in that  

 thread.


   Some of these are pretty standard interview




 questions. Although I  

 don't personally like to ask these sort of




 questions because they are  

 often about knowing a "trick" which you




 an easily lookup.  The can be  

 fun to figure out though.
  Here's another common one:
  | Write a bitcount for a 32-bit number.
  And a little more challenging:
  | Write a bitcount for a 32-bit number that is




 less then 15 operations  

 without using a lookup table.
  | Can you do that in 12 or less?
  -Joel


 int count( in int i )
 {
     int c = (i & 1) + (i & 2 ? 1 : 0) + (i


 & 4 ? 1 : 0) + (i & 8 ? 1 :  

 0);
     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i &


 4 ? 1 : 0) + (i & 8 ? 1 : 0);

     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i &


 4 ? 1 : 0) + (i & 8 ? 1 : 0);

     i >>= 4;
     c += (i & 1) + (i & 2 ? 1 : 0) + (i &


 4 ? 1 : 0) + (i & 8 ? 1 : 0);

     return c;
 }

 int count2( in int i )
 {
     int c = (i & 1) + ((i >> 1) & 1) +


 ((i >> 2) & 1) + ((i >> 3) & 1);

     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i

 2) & 1) + ((i >> 3) & 1);


     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i

 2) & 1) + ((i >> 3) & 1);


     i >>= 4;
     c += (i & 1) + ((i >> 1) & 1) + ((i

 2) & 1) + ((i >> 3) & 1);


     return c;
 }


 
 Much simpler:
 
 int getBitCount32(int i) {
      return getBitCount16(i) + getBitCount16(i >>
 16);
 }
 
 int getBitCount16(int i) {
      return getBitCount8(i) + getBitCount8(i >> 8);
 }
 
 int getBitCount8(int i) {
      return getBitCount4(i) + getBitCount4(i >> 4);
 }
 
 int getBitCount4(int i) {
      return getBitCount2(i) + getBitCount2(i >> 2);
 }
 
 int getBitCount2(int i) {
      return (i & 2) + (i & 1);
 }


 Although untested, would this qualify? I don't see any logic problems.

 int getBitCount(int i){
    int b = i & 1;
    i = i >>> 1;    //force unsigned shift
    return b + (i ? getBitCount(i) : 0);
}
Aug 15 2008