Fastest way to count number of bits in a 32-bit or 64-bit integer.

Question

Anonym · Accepted Answer

You are in google and you have almost infinite resources so you can keep a table with all the options o(1) this works for 32bit

Anonym · Answer

Should be better than linear -- optimal solution is  log(n). Search the web for the solution.

Anonym · Answer

Most efficient would be keeping a table for number bits in a byte. You need 4 lookups for 32 bit number or 8 lookups for 64 bit number. 256-entry table is small enough to fit in the cache of the highest level in virtually any CPU architecture.
Technically this is still linear solution thought.

Google

Frage im Vorstellungsgespräch bei Google

Antworten zu Vorstellungsgespräch

Beobachtete Unternehmen

Jobsuchen