## digitalmars.D.learn - Programing Puzzles

• Wyverex (11/11) Aug 06 2008 just some fun little programming puzzles I found around online...
• Wyverex (53/76) Aug 06 2008 Solutions, Don't Peek if you havn't tried them yet!
• Lutger (9/16) Aug 06 2008 this works, no semicolon needed with phobos:
• Wyverex (3/21) Aug 06 2008 Sweet! Didn't know printf was accessible without an import!
• Lars Ivar Igesund (8/10) Aug 07 2008 Actually this is due to a bad decision early on, where printf was put in...
• BCS (14/24) Aug 06 2008 void DoIt(int i = 1)
• Wyverex (5/5) Aug 06 2008 Through another one in....
• Wyverex (20/29) Aug 06 2008 import tango.io.Stdout;
• BCS (13/21) Aug 06 2008 int Mul(int i, int j)
• BCS (8/8) Aug 06 2008 char a=0,b=0,c=0,d=0;
• Wyverex (11/26) Aug 06 2008 import std.stdio;
• BCS (2/30) Aug 06 2008 yah, that looks right. I think I used a comma expression or some sutch.
• Koroskin Denis (9/19) Aug 06 2008 =
• BCS (5/28) Aug 06 2008 isPowerOfTwo(int.min);
• JAnderson (7/42) Aug 06 2008 What are you trying to say? I imagine your validating Koroskin solution...
• BCS (2/11) Aug 08 2008 byte.min < 0, all powers of 2 are gratter than zero
• BCS (2/14) Aug 08 2008 OTOH my solution fails in the same case :(
• JAnderson (4/22) Aug 09 2008 ic, I was thinking unsigned byte. Pretty easy to test for if you need
• JAnderson (12/21) Aug 06 2008 Some of these are pretty standard interview questions. Although I don't
• Wyverex (23/53) Aug 07 2008 int count( in int i )
• Koroskin Denis (18/64) Aug 07 2008 Much simpler:
• JAnderson (11/86) Aug 07 2008 That's an ok solution although a little complecated for question 1. It
• Koroskin Denis (3/84) Aug 08 2008 Ah, I know where you got it from :) Scroll down, there is also a solutio...
• JAnderson (5/96) Aug 08 2008 I know the answer for 15 / 12 ops I was asking the question. Also what
• Koroskin Denis (4/103) Aug 08 2008 It looks like a copy-paste from bithacks
• bearophile (8/11) Aug 08 2008 My libs (math module) already contain some translations to D of those "h...
• JAnderson (6/113) Aug 09 2008 Actually I have been there before. The code was from some old project
• Don (4/111) Aug 14 2008 My solution is already on that page -- look for my name . 14 ops, if
• Koroskin Denis (3/27) Aug 07 2008 I know the solution for 15 operations, but it is impossible to come up
• JAnderson (5/41) Aug 07 2008 The 12 op solution doesn't require 64-bit. Your right though to come up...
• Era Scarecrow (8/99) Aug 15 2008 Although untested, would this qualify? I don't see any logic problems.
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
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
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
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
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
```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
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
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
```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
```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
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
```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
"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=

nt  =

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

// 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
```BCS wrote:

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.

// 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
```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
```Reply to Benjamin,

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
```BCS wrote:

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

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

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

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

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

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

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
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:
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
```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

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

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
1 sub, 4 adds, 3 ands, 3 shifts, 3 rotates.
```
Aug 14 2008
"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

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

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
Era Scarecrow <rtcvb32 yahoo.com> writes:
```Koroskin Denis 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

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