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)



Problem #1 Write a "Hello World" program in D with only a semicolon on 
import statement.

Problem #2 Test if an int is even or odd without looping or if statement 
(Cant use: do, while, for, foreach, if).

Problem #3 Write a program without using any loop (if, for, while etc) 
to print numbers from 1 to 100 and 100 to 1;

Problem #4 Find if the given number is a power of 2.



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)
 
 
 
 Problem #1 Write a "Hello World" program in D with only a semicolon on 
 import statement.
 
 Problem #2 Test if an int is even or odd without looping or if statement 
 (Cant use: do, while, for, foreach, if).
 
 Problem #3 Write a program without using any loop (if, for, while etc) 
 to print numbers from 1 to 100 and 100 to 1;
 
 Problem #4 Find if the given number is a power of 2.
 
 
 
 Post Solutions to this root, comments to someones solution in that thread.

Solutions, Don't Peek if you havn't tried them yet! Problem #1******************************************** import tango.io.Stdout; void main() { if(Stdout("Hello World")) {} } Problem #2********************************************* import tango.io.Stdout; void main() { int x = 2; char[][2] ans = ["Even", "Odd"]; Stdout( ans[ x & 1 ] ).newline; } Problem #3******************************************* 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); } Problem#4****************************************** 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:
 
 Problem #1********************************************
 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:
  
 Problem #1********************************************
 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...
 
 Problem #2 Test if an int is even or odd without looping or if
 statement (Cant use: do, while, for, foreach, if).

bool isEven(int i) {return !(i & 0x01);}
 
 Problem #3 Write a program without using any loop (if, for, while etc)
 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); }
 
 Problem #4 Find if the given number is a power of 2.
 

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.
 

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)



 Problem #1 Write a "Hello World" program in D with only a semicolon on=

 import statement.

 Problem #2 Test if an int is even or odd without looping or if stateme=

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

 Problem #3 Write a program without using any loop (if, for, while etc)=

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

 Problem #4 Find if the given number is a power of 2.

// 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)
 
 Problem #1 Write a "Hello World" program in D with only a semicolon
 on  import statement.
 
 Problem #2 Test if an int is even or odd without looping or if
 statement  (Cant use: do, while, for, foreach, if).
 
 Problem #3 Write a program without using any loop (if, for, while
 etc)  to print numbers from 1 to 100 and 100 to 1;
 
 Problem #4 Find if the given number is a power of 2.
 

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)

 Problem #1 Write a "Hello World" program in D with only a semicolon
 on  import statement.

 Problem #2 Test if an int is even or odd without looping or if
 statement  (Cant use: do, while, for, foreach, if).

 Problem #3 Write a program without using any loop (if, for, while
 etc)  to print numbers from 1 to 100 and 100 to 1;

 Problem #4 Find if the given number is a power of 2.

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


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


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...
 
 
 Problem #2 Test if an int is even or odd without looping or if statement 
 (Cant use: do, while, for, foreach, if).
 
 Problem #4 Find if the given number is a power 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
Aug 06 2008
next sibling parent reply Wyverex <wyverex.cypher gmail.com> writes:
JAnderson wrote:
 Wyverex wrote:
 just some fun little programming puzzles I found around online...


 Problem #2 Test if an int is even or odd without looping or if 
 statement (Cant use: do, while, for, foreach, if).

 Problem #4 Find if the given number is a power 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; }
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...


 Problem #2 Test if an int is even or odd without looping or if 
 statement (Cant use: do, while, for, foreach, if).

 Problem #4 Find if the given number is a power of 2.

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

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


 Problem #2 Test if an int is even or odd without looping or if 
 statement (Cant use: do, while, for, foreach, if).

 Problem #4 Find if the given number is a power of 2.

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

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

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


 Problem #2 Test if an int is even or odd without looping or if 
 statement (Cant use: do, while, for, foreach, if).

 Problem #4 Find if the given number is a power of 2.

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

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

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

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


 Problem #2 Test if an int is even or odd without looping or if 
 statement (Cant use: do, while, for, foreach, if).

 Problem #4 Find if the given number is a power of 2.

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

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

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

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!

you have access to rotation. 1 sub, 4 adds, 3 ands, 3 shifts, 3 rotates.
Aug 14 2008
prev sibling next sibling parent "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...


 Problem #2 Test if an int is even or odd without looping or if  
 statement (Cant use: do, while, for, foreach, if).

 Problem #4 Find if the given number is a power of 2.

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

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
prev sibling next sibling parent "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...


 Problem #2 Test if an int is even or odd without looping or if  
 statement (Cant use: do, while, for, foreach, if).

 Problem #4 Find if the given number is a power of 2.

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

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

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
prev sibling parent "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...


 Problem #2 Test if an int is even or odd without looping or if  
 statement (Cant use: do, while, for, foreach, if).

 Problem #4 Find if the given number is a power of 2.

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

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

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

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
prev 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)
    Problem #1 Write a "Hello World" program in D with only a semicolon  
 on import statement.
  Problem #2 Test if an int is even or odd without looping or if  
 statement (Cant use: do, while, for, foreach, if).
  Problem #3 Write a program without using any loop (if, for, while etc)  
 to print numbers from 1 to 100 and 100 to 1;
  Problem #4 Find if the given number is a power of 2.
    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)
    Problem #1 Write a "Hello World" program in D with only a 
 semicolon on import statement.
  Problem #2 Test if an int is even or odd without looping or if 
 statement (Cant use: do, while, for, foreach, if).
  Problem #3 Write a program without using any loop (if, for, while 
 etc) to print numbers from 1 to 100 and 100 to 1;
  Problem #4 Find if the given number is a power of 2.
    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