Goldman Sachs Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
int count(int n)
{
int c = 0;
while(n>0)
{
if(n | 1 == 1) // ORing the number with 1 gives 1 if the right most bit is '1'
{
c++;
}
n = n >> 1;
}
return c;
}
shouldn't you AND it with 1. ORing with 1 will always yield 1 even if the rightmost bit is 0.
int x; // number (32 bits)
x = (x & 0x55555555) + ((x & 0xaaaaaaaa)>>1); // 0..2 ones in 2 bits
x = (x & 0x33333333) + ((x & 0xcccccccc)>>2); // 0..4 ones in 4 bits
x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4); // 0..8 ones in 8 bits
x = x + (x >> 8); // 0..16 ones in 8 bits
x = x + (x >> 16); // 0..32 ones in 8 bits
x &= 0xff;
This is the fastest but the worst response you could give in an interview. How do you explain or deduce this in an interview? Apart from "I searched for popcount on google and memorized this"....
well they certainly do not expect you to invent a bike on the interview)) but you can explain the logic behind it to make sure you understand - then you don''t need to memorize it "by hearth"
the logic is in fact pretty easy:
in the first step we count ones in each group of two bits
this is done by ((x & 1010101...) >> 1) + (x & 01010101...)|
then we repeat the same op but now for each group of 4 bits
with the masks 110011001100... and 001100110011.. resp.
btw once you get this algorithm you can apply a similar idea to other bit manipulation e.g. bit reversal or finding the highest bit set..
i think it will be in O(log n) using this code
int count(int n)
{
int c = 0;
while(n>0)
{
if(n%2 == 1)
{
c++;
}
n/=2;
}
return c;
}
int x; // number (32 bits)
x = (x & 0x55555555) + ((x & 0xaaaaaaaa)>>1); // 0..2 ones in 2 bits
x = (x & 0x33333333) + ((x & 0xcccccccc)>>2); // 0..4 ones in 4 bits
x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4); // 0..8 ones in 8 bits
x = x + (x >> 8); // 0..16 ones in 8 bits
x = x + (x >> 16); // 0..32 ones in 8 bits
x &= 0xff;
better
If you subtract -1 from a given number it will convert the last "1" bit to "0" followed by continuous tail of 1, remove 1's tail by taking "&"
- Wayne March 17, 2012