Search code examples
hashmapbitlookup-tables

Lookup table for counting number of set bits in an Integer

Was trying to solve this popular interview question - http://www.careercup.com/question?id=3406682

There are 2 approaches to this that i was able to grasp -

  1. Brian Kernighan's algo - Bits counting algorithm (Brian Kernighan) in an integer time complexity

  2. Lookup table.

I assume when people say use a lookup table, they mean a Hashmap with the Integer as key, and the count of number of set bits as value.

How does one construct this lookup table? Do we use Brian's algo to to count the number of bits the first time we encounter an integer, put it in hashtable, and next time we encounter that integer, retrieve value from hashtable?

PS: I am aware of the hardware and software api's available to perform popcount (Integer.bitCount()), but in context of this interview question, we are not allowed to use those methods.

Solution

  • Integers can directly be used to index arrays; e.g. so you have just a simple array of unsigned 8bit integers containing the set-bit-count for 0x0001, 0x0002, 0x0003... and do a look up by array[number_to_test].

    You don't need to implement a hash function to map an 16 bit integer to something that you can order so you can have a look up function!