Programing Puzzles

[Koroskin Denis]

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!