Programing Puzzles

[Koroskin Denis]

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

> 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

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