avocadia

# la résolution des problèmes de l'escalier

I was asked today to write a function to calculate the number of bits set in a given integer. That is, there is one bit set in 4 (100), but two bits set in 5 (101) .
```
int CountOfBitsSet(int n) {
  int count = 0;
  while (n > 0) {
    if (n%2 == 1) 
      count++;

    n = n >> 1;
  }
  return count;
}
```
The follow up question was the maximum number of times the main loop would..err…loop¹. The follow up to that was how I could optimise it. I didn’t know, and it was suggested to me that you could use a lookup table. I agreed that if it was something that was likely to remain in memory for awhile and be used a lot, you could maintain a hash of previously calculated values, but what they were really getting at was a lookup table that is preloaded. That’s a lot of memory, that is for just over 2.1 billion numbers.

Obviously the last follow up question was how you could optimise this ridiculous unhelpful lookup table. I couldn’t think of one, I was too distracted by how ridiculously unhelpful that lookup table would be and just suggested that I wouldn’t do that, I’d just use a populated-as-generated hash.

There’s a term for thinking of the perfect comeback ten minutes too late; is there one for thinking of a good answer to a question a few hours later²?

It’s in Ruby instead of the C# I was being tested in. Since they weren’t testing me in the language so much as problem solving, I’m quite sure it wouldn’t have mattered.
```
class BitCounting
  LOOKUPS =  {"0"=>0, "1"=>1, "2"=>1, "3"=>2, "4"=>1, "5"=>2, "6"=>2, "7"=>3, "8"=>1, "9"=>2, "a"=>2, "b"=>3, "c"=>2, "d"=>3, "e"=>3, "f"=>4}

  def self.numBitsSet(n)
    hex_ver = n.to_s(base=16)
    count = 0
    (0..hex_ver.length-1).each{|digit|count += LOOKUPS[hex_ver[digit]]}
    count
  end
end
```
Maximum number of iterations through the loop drops to 8, and the lookup table has a negligible footprint.

Bah!

¹ 31.

² Apart from too bloody late by half.
- gilmae
- 26/08/2009
- - code

avocadia

# la résolution des problèmes de l'escalier

Meta

Feeds

Links