Programing Puzzles

[JAnderson]

Koroskin Denis wrote:
> On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher at 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.
>>>   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