Domanda di colloquio di Google

Find the number f set bits in an integer

Risposte di colloquio

Anonimo

12 lug 2010

>>> is a bit shift with 0 fill. Since it's an integer, the first bit may be 1 if it is negative, in which case a normal bit shift may cause more 1's to come in.

Anonimo

12 lug 2010

referring to the groups of 1's.... assuming the groups of 1's can be of any size (i.e. 010, 0110, 01110, etc), then all you need to do is count the number of "10" occurrences in the sequence of bits.

Anonimo

13 lug 2010

For the number of set bits in an integer. The mask and shift should do the trick. But if we have 2^32 bytes of memory available, I would go with a lookup table for an O(1) instead of O(n) complexity. An intermediate solution could use a mapping for a single byte instead of the complete integer, then doing four successive shift and mask operations.

Anonimo

13 lug 2010

For the group of 1's in an array. Assuming the array starts with a '0', I would count the "01" sequences.