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.

Community
  • 1
  • 1
Quest Monger
  • 8,252
  • 11
  • 37
  • 43

3 Answers3

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.

BitMask
  • 314
  • 2
  • 9
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!

Marcus Müller
  • 34,677
  • 4
  • 53
  • 94
  • 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. – Quest Monger Jul 09 '15 at 00: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). – Marcus Müller Jul 09 '15 at 06: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! – Quest Monger Jul 09 '15 at 07:08
  • :) You also have to realize that a table with 2^16 entries of one byte length is practically negligible – Marcus Müller Jul 09 '15 at 07:15
  • 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) – Marcus Müller Jul 09 '15 at 07:17
  • 1
    so that it's not even 16kB, but 4kB. – Marcus Müller Jul 09 '15 at 07: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.

Zitrax
  • 19,036
  • 20
  • 88
  • 110
Vamshi
  • 437
  • 6
  • 14