Interview Question for Software Development Engineer In Test at Amazon.com:

It started out with an ambiguous set-up so the first thing that needed to be figured out was what kind of number to be taken in. How many bits this value was. I was told to assume it was 32 bits. I mentioned that the number may be in 2's complement, I was told to only expect unsigned integers. The solution is pretty straight forward, it only requires a for loop that counts from 0 to 31 and checks whether the integer masked with 1 is equal to 1. If it is, add one to the accumulator and shift a bit to the right. Then I was told to extend this function to work for an n bit integer. With some hints I figured out that log base 2 of a number gave you the maximum number of bits it would take to store that number so simply replace the loop that went from 0 to 31 with a loop that goes from 0 to log_2(n).

If the task is only for positive numbers, then my solution would be:

bool is_odd_set_bits(unsigned number)
{
    bool result = false;
    int n = number;

    do
    {
        result |= ((n % 2) == 1);
        n /= 2;
    }
    while ((n / 2) != 0);

    return result;
}

<?php
        // O(log2(n)) times
    function evenOrodd($num)
    {
        $result=0;
        while($num!=0)
        {
            if($num%2==1)
                $result++;
            $num = $num/2;
        }
        return ($result%2==1)?"odd" : "even";
    }
?>

mod and div operators are good, but you could set yourself apart by using a more efficient algorithm. In terms of big O, it will be the same, but it will have a higher throughput since the operations are slightly faster.

<<Modifying Tim's base code>>
bool is_odd_set_bits(unsigned number)
{
    bool result = false;
    int n = number;

    while(n != 0)
    {
        result |= ((n & 0x01) == 1);
        n >> 1;
    }

    return result;
}

masking is faster than a mod operator, and bit shifting is faster than divisions

i was trying this in java and found kinda small bug... so we should return false if the number is 3 which is 0000000011.
I guess changing the line to:
result ^= ((n & 0x01) == 1);
will do the job...