Programing Puzzles
JAnderson
ask at me.com
Fri Aug 8 08:35:39 PDT 2008
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
More information about the Digitalmars-d-learn
mailing list