Programing Puzzles

[Don]

Koroskin Denis wrote:
> On Fri, 08 Aug 2008 19:35:39 +0400, JAnderson <ask at me.com> wrote:
> 
>> Koroskin Denis wrote:
>>> 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.
>>
>> 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.