The Computer Machine Whisperer

When I was searching for my current job, I got a lot of help from Joel Spolsky’s Guerrilla Guide to Interviewing. I found that a few of my phone interviewers were readers of Joel’s when one (who was not affiliated with Fog Creek Software) asked me:

“How many gas stations are in Los Angeles?”

Right out of the article, and the only one with an answer below it in said article, which I happened to have laid out in front of me at the time. I had to add a few candidate categories to Joel’s list:

• Not-so-smart candidates will get flustered and upset.
• Smart candidates will realize you aren’t quizzing them on their knowledge, but on their problem-solving abilities.
• Smart-ass candidates will say “I’d just go to Joel on Software and look up the answer.”
• Smart smart-ass candidates will read the answer off of JoS and wing it. No sense in letting them know you’ve figured out they’re a lazy interviewer.

I’ve always enjoyed a good challenge, and hadn’t written any C code in awhile, so I decided to tackle a few of his coding questions, like reversing a string in place:

void revstr(TCHAR *str)
{
    if( *str == '' )
    {
        return;
    }

    TCHAR *start = str;
    TCHAR *end = start + strlen(str) - 1;

    while(start < end)
    {
        *start ^= *end;
        *end ^= *start;
        *start ^= *end;
        *start++;
        *end–;
        /*

        could also use *start ^= *end ^= *start++ ^= *end–; if you want to get fancy
        */
    }
}

That led me to try my hand at a function to check if a string was a palindrome:

bool isAlphaNumeric(char c)
{
    return (iswalpha(c) || iswdigit(c));
}

bool isPalindrome(char *str)
{
    /* A man, a plan, Anal Panama!!! */
    if(*str == ”)
    {
        return false;
    }

    int len = strlen(str);
    if(len <= 1) return true;

    char *start = str;
    char *end = start + len - 1;

    while(start < end)
    {
        if(!isAlphaNumeric(*start))
        {
            *start++;
            continue;
        }
        if(!isAlphaNumeric(*end))
        {
            *end–;
            continue;
        }
        if(towlower(*start) != towlower(*end))
        {
            return false;
        }
        *start++;
        *end–;
    }
    return true;
}

Nothing too special for either of those. Feel free to use them if they’re useful to you, just don’t pretend you wrote them if you didn’t. I’m personally stealing them from the 2005 version of myself, but to be fair, he slept with my wife, so we’re even.

The point of all this code dick-waving has been what I thought was the really interesting question on Joel’s test: Count all the bits that are on in a byte.

A simple, but inefficient method is to just use a bitwise AND to see if the lowest bit is set, then shift the number one place to the right, and repeat until it’s zero, incrementing a counter each time you come across a set bit. However, unless you’re storing it in a lookup table of some sort, you’ll have to run that code each time you need it. With a lookup table, you can cache it the first time it’s needed, and do a simple lookup every time after that. If you’re willing to get even fancier and think about the problem, you can save a hell of a lot of space.

As a disclaimer, my method is far from the best. The best I’ve seen comes from a few mathematical geniuses and can be found here. Even though I failed CALC 166 in college (who schedules Calculus at 7:30 in the morning?), I’ve always been fascinated with math and numbers, and the odd patterns that show up in them. For example, both my zip code and cell phone number (including the area code) are prime numbers, and my office phone number is made up entirely of different powers of two.

So, when Joel said “Really, really brilliant candidates will try to devise a way to compute the table using some kind of a shortcut taking advantage of the patterns that occur.,” I took that as a challenge to find the patterns, and I believe I have. To start, here are the number of bits set for each number that can be represented in a byte. I went ahead and displayed them as NxN grids, where N is a power of two representing the maximum number of bits in the given number, so these represent 2-, 4-, and 8-bit numbers, respectively.

0-3 in 2x2 grid

0 	1
1 	2

0-15 in 4×4 grid

0 	1 	1 	2
1 	2 	2 	3
1 	2 	2 	3
2 	3 	3 	4

0-255 in 16×16 grid

0 	1 	1 	2 	1 	2 	2 	3 	1 	2 	2 	3 	2 	3 	3 	4
1 	2 	2 	3 	2 	3 	3 	4 	2 	3 	3 	4 	3 	4 	4 	5
1 	2 	2 	3 	2 	3 	3 	4 	2 	3 	3 	4 	3 	4 	4 	5
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
1 	2 	2 	3 	2 	3 	3 	4 	2 	3 	3 	4 	3 	4 	4 	5
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
3 	4 	4 	5 	4 	5 	5 	6 	4 	5 	5 	6 	5 	6 	6 	7
1 	2 	2 	3 	2 	3 	3 	4 	2 	3 	3 	4 	3 	4 	4 	5
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
3 	4 	4 	5 	4 	5 	5 	6 	4 	5 	5 	6 	5 	6 	6 	7
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
3 	4 	4 	5 	4 	5 	5 	6 	4 	5 	5 	6 	5 	6 	6 	7
3 	4 	4 	5 	4 	5 	5 	6 	4 	5 	5 	6 	5 	6 	6 	7
4 	5 	5 	6 	5 	6 	6 	7 	5 	6 	6 	7 	6 	7 	7 	8

Notice anything in particular about the numbers when they’re laid out like this? The first row and column have exactly the same numbers, and if you pick a row and column, and add the first number of each together, it’s the exact number you’ll find at the point that row and column intersect. I’m also showing them as 2D arrays, but if you lay out the 2×2 grid as a 1D array, compare it to the first row and column of the 4×4 grid, and then do the same with that grid compared to the 16×16 grid. Each grid, if treated as a one-dimensional array, forms the basis of the next one. There are also some other cool patterns I will mention, but won’t go into.

So, now that we know that we can take the row and column and use that to figure out how many bits are set, we can just divide and mod the number we want by the square root of the size of the array to get our coordinates, like so:

# say we’re looking for the number of bits in 243

x = 243 / 16 => 15 (int)
y = 243 % 16 => 3

# or, if you’re using Ruby
x,y = 243.divmod(16) => [15,3]

Since we’re going to use these coordinates as indices into arrays, and the arrays are the same, we can just use the same array for both, the first row of the grid:

# 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

# Let's call the array "a" add the two indices we got earlier together

a[3] + a[15] = 2 + 4 = 6

# Are there six bits set in the number 243?
243 = 11110011 # Indeed there are

So, your lookup table for an N-bit number requires only 2^(N/2) entries (thanks for the correction, nico). Instead of 256 bytes to cache the number of bits in an 8-bit number, you need at most only 16 bytes. Given that I showed how each grid formed the first row of the next grid, and depending on how you decide to trade off between speed and storage, you could get away with only storing the base array of [0,1,1,2] and computing each successive grid from there. I actually did this in the Ruby code I used to generate the grid tables above, which you can see here:

class Fixnum

    @@bits_base = [0,1,1,2]

    def bits
        self.divmod(@@bits_base.length).inject(0){|sum, i| sum += @@bits_base[i]}
    end

    def update_bits_base(new_bits_base)
        @@bits_base = new_bits_base
    end
end

class Array

    def in_groups_of(n)
      list=[]
      i = 0

      while(i < length) do
        list << slice(i, n)
        i += n
      end

      list
    end

    def print_table(size, col_sep_begin = nil, col_sep_end = “\t“, row_sep_begin = nil, row_sep_end = “\n“, prefix = nil, suffix = nil)
        row_arr = self.in_groups_of(size).inject(“”){|row, row_item| col_arr = row_item.inject(“”){|col, col_item| col + “#{col_sep_begin}#{col_item}#{col_sep_end}“}; row + “#{row_sep_begin}#{col_arr}#{row_sep_end}“}
        puts “#{prefix}#{row_arr}#{suffix}“

    end

    def print_html_table(size)
        print_table(size, “<td>“, “</td>“, “<tr>“, “</tr>“, “<table>“, “</table>“)
    end

end

def bits_on_test(size)
    sqrt_size = Math.sqrt(size).to_i

    puts “<p>0-#{size-1} in #{sqrt_size}x#{sqrt_size} grid<hr /></p>“

    bits = (0..(size-1)).map{|i| i.bits}
    bits.print_table(sqrt_size)

    bits
end

[1,2,4].each { |i|
    i.update_bits_base(bits_on_test(2**(2*i)))
}

The important part is the Fixnum::bits method, which just does the divmod outlined above and sums the array values at those indices. @@bits_base is the lookup table, which is re-computed using itself as the first row and column.

Now, for the other cool pattern I noticed, but won’t go into too much detail on. It might help to have a pen and paper.

# Make a 4x4 grid on the paper, and fill in the upper left quadrant with the values of the 2x2 grid.
# For each quadrant, add the value from that same quadrant in the 2x2 grid to the array.

# Upper left quad add 0 to each number from 2x2
0 	1 	* 	*
1 	2 	* 	*
* 	* 	* 	*
* 	* 	* 	*

# Upper right quad add 1 to each number from 2×2
0 	1 	1 	2
1 	2 	2 	3
* 	* 	* 	*
* 	* 	* 	*

# Lower left quad add 1 to each number from 2×2
0 	1 	1 	2
1 	2 	2 	3
1 	2 	* 	*
2 	3 	* 	*

# Lower right quad add 2 to each number from 2×2
0 	1 	1 	2
1 	2 	2 	3
1 	2 	2 	3
2 	3 	3 	4

Does the final grid look familiar? Compare it to the 4×4 grid I computed earlier. Now applying the same principle to this 4×4 grid to make an 8×8, and then a 16×16 grid, and you’ll come up with the 16×16 grid I came up with above. If you’re clever enough, you may come up with some sort of quadtree algorithm to determine what additions you’d have to make to the base [0,1,1,2] array for a given number.

I hope this has made at least some sense to you. If it does, then Wooo! Independent verification from Joel that I’m really, really brilliant. If not, then my secret fear that I’m actually retarded and everyone is just humoring me may be true. Personally, I’d put my money on idiot savant.