Question d’entretien chez Google

Find the number f set bits in an integer

Réponses aux questions d'entretien

Utilisateur anonyme

12 juil. 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.

Utilisateur anonyme

12 juil. 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.

Utilisateur anonyme

13 juil. 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.

Utilisateur anonyme

13 juil. 2010

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