Electronic Arts Interview Question
Software Engineer / Developersint mask = 0x01;
int count = 0;
while (mask)
{
if ((num & mask) == mask)
count++;
mask <<= 1;
}
Basically, we have a number:
xxxxxxxx
And we try to check whether each bit is set or not. So we start off with the extreme right (least significant) bit, 0x01, which will be 00000001 (in case of an eight bit number). Remember: regardless of the number of bits of the number, the LSB will always be 1 for 0x01.
Now we bitwise AND it.
xx x xx xxx
&00000001
If the last bit is 1 then we should get this same 0x01 number back.
The logic is the same for the rest of the bits. To get them, we simply left shift the mask every time by 1.
And once the mask is 10000000, and then it is shifted again, it becomes 00000000.
Thus mask is not non-zero any longer, and quits the while loop.
This is a good solution but at the very last step, suppose we have the value 00000010 and then we clear the bit. Then the value 0 will be assigned to num, which is false. Hence it doesn't count the last 1. Thus it is better to separate the statements like so:
count = 0;
while (num)
{
num &= num-1; // Note that there has to be atleast one 1 if the number is greater than 0. If it isn't, it won't even enter the while loop
count++;
}
- Anonymous September 14, 2012