Koroskin Denis wrote:
> On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher@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

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

> Koroskin Denis wrote:
>> On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher@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.

Koroskin Denis wrote:
> On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask@me.com> wrote:
> 
>> Koroskin Denis wrote:
>>> On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher@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

On Fri, 08 Aug 2008 19:35:39 +0400, JAnderson <ask@me.com> wrote:

> Koroskin Denis wrote:
>> On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask@me.com> wrote:
>>
>>> Koroskin Denis wrote:
>>>> On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher@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!

Koroskin Denis:
> It looks like a copy-paste from bithacks (http://graphics.stanford.edu/~seander/bithacks.html) - a must read for everyone!

My libs (math module) already contain some translations to D of those "hacks", including this one.

That page is good, and things will be better as soon as a high enough level language (D?) will allow to use CPU vector instructions like SSE and the following ones with a simple enough syntax, we'll probably see 1024 bit ones in 2-4 years:
http://en.wikipedia.org/wiki/Advanced_Vector_Extensions
With 1024 bits you can do *lot* of bitwise computations in one/few clock tick(s) :-)
There are many algorithms (like building state machines for exact/approximate string matching) that can become much faster with a portable support of such CPU instructions (you can use SSE3 with GCC in C but the syntax is hairy and not standard).

Bye,
bearophile

Reply to janderson,


> What are you trying to say?  I imagine your validating Koroskin
> solution.
> 
> 10000000  == byte.min
> 01111111  == byte.min - 1
> =
> 00000000  == is power of 2
> -Joel
> 

byte.min < 0, all powers of 2 are gratter than zero

Reply to Benjamin,

> Reply to janderson,
> 
>> What are you trying to say?  I imagine your validating Koroskin
>> solution.
>> 
>> 10000000  == byte.min
>> 01111111  == byte.min - 1
>> =
>> 00000000  == is power of 2
>> -Joel
> byte.min < 0, all powers of 2 are gratter than zero
> 

OTOH my solution fails in the same case :(

Koroskin Denis wrote:
> On Fri, 08 Aug 2008 19:35:39 +0400, JAnderson <ask@me.com> wrote:
> 
>> Koroskin Denis wrote:
>>> On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask@me.com> wrote:
>>>
>>>> Koroskin Denis wrote:
>>>>> On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher@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!

Actually I have been there before.  The code was from some old project of mine,  I just wanted to make sure I got it right (with out having to think about it and have someone complain that I forgot a ; or something).  However maybe that was originally from bithacks.

-Joel

BCS wrote:
> Reply to Benjamin,
> 
>> Reply to janderson,
>>
>>> What are you trying to say?  I imagine your validating Koroskin
>>> solution.
>>>
>>> 10000000  == byte.min
>>> 01111111  == byte.min - 1
>>> =
>>> 00000000  == is power of 2
>>> -Joel
>> byte.min < 0, all powers of 2 are gratter than zero
>>
> 
> OTOH my solution fails in the same case :(
> 
> 

ic, I was thinking unsigned byte.  Pretty easy to test for if you need to use unsigned numbers in that range.

-Joel

Koroskin Denis wrote:
> On Fri, 08 Aug 2008 19:35:39 +0400, JAnderson <ask@me.com> wrote:
> 
>> Koroskin Denis wrote:
>>> On Fri, 08 Aug 2008 07:47:03 +0400, JAnderson <ask@me.com> wrote:
>>>
>>>> Koroskin Denis wrote:
>>>>> On Thu, 07 Aug 2008 19:37:27 +0400, Wyverex <wyverex.cypher@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.