2

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.

1
  • not a hashmap - the hash would be an useless indirection here.
    – foo
    Dec 15, 2022 at 19:59

3 Answers 3

7

I was looking for Answer everywhere but could not get the satisfactory explanation.

Let's start by understanding the concept of left shifting. When we shift a number left we multiply the number by 2 and shifting right will divide it by 2.

For example, if we want to generate number 20(binary 10100) from number 10(01010) then we have to shift number 10 to the left by one. we can see number of set bit in 10 and 20 is same except for the fact that bits in 20 is shifted one position to the left in comparison to number 10. so from here we can conclude that number of set bits in the number n is same as that of number of set bit in n/2(if n is even).

In case of odd numbers, like 21(10101) all bits will be same as number 20 except for the last bit, which will be set to 1 in case of 21 resulting in extra one set bit for odd number.

let's generalize this formual

number of set bits in n is number of set bits in n/2 if n is even
number of set bits in n is number of set bit in n/2 + 1 if n is odd (as in case of odd number last bit is set. 

More generic Formula would be:

BitsSetTable256[i] = (i & 1) +  BitsSetTable256[i / 2];

where BitsetTable256 is table we are building for bit count. For base case we can set BitsetTable256[0] = 0; rest of the table can be computed using above formula in bottom up approach.

2

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!

6
  • Thank you for clarifying that. Can you explain how one would go about determining the 'set-bit-count ' for the said integers in the first place? The reason i ask this is because the method used to determine the popcount for the lookup table adds to the Time complexity of the overall system. Jul 9, 2015 at 0:48
  • 1
    @QuestMonger: This depends on how you understand the interview question.But if you don't consider program size a part of the complexity of the problem,you'd just ship the precomputed table with your program.But that's the whole point of these kind of questions:Are you able to discuss these points?I really sigh at websites like the one you cite because they assume Google treats interviews like your city treats driving license questionaries:it's not like that.There might be multiple acceptable answers,and the interview is about finding out how much you understand (rather than know by heart). Jul 9, 2015 at 6:54
  • Very true. Unfortunately, the interview situation is a lot worse now, with screening interviews being automated and no human convo involved (hackerrank, codility, etc). The bit about shipping lookup tables is very interesting. I was operating under the assumption that i had to do everything from scratch. I will keep that in mind. Thanks! Jul 9, 2015 at 7:08
  • 1
    and if you're really hacky enough, you can get away with a table of one fourth of that size (only store set numbers of bits for even numbers [because the following odd one simply has one more], and using only four bit to store the number) Jul 9, 2015 at 7:17
  • 1
    so that it's not even 16kB, but 4kB. Jul 9, 2015 at 7:17
2

To answer your question about how to compute this table:

int table[256]; /* For 8 bit lookup */
for (int i=0; i<256; i++) {
    table[i] = table[i/2] + (i&1);
}

Lookup this table on every byte of the given integer and sum the values obtained.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.