There are two main advantages to choosing the exponent 2<sup>16</sup>+1. 

The first advantage, as Johannes observed, is that for fixed size exponent, exponentiation to power e using the <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring">basic repeated squaring method</a> is moderately faster when e has lots of zero bits. It is not true that exponents with more one bits are necessarily slower since there are plenty of such numbers with very short <a href="http://en.wikipedia.org/wiki/Addition-chain_exponentiation">addition chains</a> (though finding such short addition chains is an NP complete problem in general). In any case, if this were the only constraint then e = 3 would be a much better choice than e = 2<sup>16</sup>+1.

The second advantage is that 2<sup>16</sup>+1 is a prime number and it is not too small. A requirement of the RSA algorithm is that the exponent e must be relatively prime with &phi;(pq) = (p-1)(q-1). Since the large primes p and q are chosen randomly, there is always a chance that (p-1)(q-1) is not relatively prime with the (previously chosen) exponent e and the primes p,q must therefore be discarded. So e = 3 is a very poor choice since it is expected that every third choice of p and q would be a bad one. Choosing e to be a prime makes the probability of picking bad p and q around 1/e. So choosing e to be a large prime would be best, but too large an e would make exponentiation slow. In the end, e = 2<sup>16</sup>+1 is a nice compromise value.