"Compressing" rationals given error bounds
Continued fractions are an efficient way to enumerate rational numbers that are a good approximation of your number $x$.  In particular, given a real number $x$, you can generate a sequence of truncated continued fractions $a_i/b_i$, where each rational number $a_i/b_i$ is a better approximation to $x$ than any other fraction whose denominator is $\le b_i$.  So, a reasonably good algorithm for your problem is to compute the sequence of truncated continued fractions, and keep the last one whose denominator is smaller than your bound.  This doesn't find the best rational approximation for a given number of bits, but it does give you a best rational approximation for a given upper bound on the size of the denominator.

To compare to KWillets' excellent answer: KWillets' method takes something like $\Theta(a+b)$ steps, but finds the optimal solution (measured by bits).  Continued fractions takes something like $\Theta(\lg b)$ steps, but isn't guaranteed to find the optimal answer (measured by number of bits); it's only guaranteed to find the optimal answer if you measure by the size of the denominator.  KWillets' method seems better if $a,b$ are not too large.  However, if they are very large, then a continued fractions-based method might become more attractive.