Programing Puzzles
Koroskin Denis
2korden at gmail.com
Thu Aug 7 09:11:04 PDT 2008
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);
}
More information about the Digitalmars-d-learn
mailing list