It is possible, when encoding symbols using an arithmetic coder, to output blocks of bits and still handle underflow bits. The algorithm I am describing is based on the implementation of an arithmetic coder presented in the article "Arithmetic Coding for Data Compression" by Ian H. Witten, Radford M. Neal, and John G Cleary in the June 1987 "Communications of the ACM". The algorithm is quite different but the end result is the same except the output bytes are filled from left to right. The variable names used (High, Low and Code) are from the code examples provided with the article "Arithmetic Coding + Statistical Modeling = Data Compression Part 1 - Arithmetic Coding" by Mark Nelson in "Dr. Dobb's Journal" February, 1991 where I got my first understanding of arithmetic coding. View Sample Code.

What to Write
It is easy to determine which bits to write after the new values for High and Low are calculated by building a mask from High and Low. The formula for the mask using C++ notation is mask=(high^low)^((low&(high^low))<<1). The highest set bit in the mask will be aligned with the last bit to be written. The index of the highest set bit must be determined by one of several methods. Assembly language offers Bit Scan Reverse. The index can also be extracted from the exponent after converting the mask to a floating-point number. Low is shifted to the right by the index to obtain the value to be written. To calculate the number of bits to write, subtract the index from the number of bits used for Low (sizeof(Low)*8-index).

Handling Bit output and Underflow
The bits to be written contain all the bits that match, the first non-matching bit, and the underflow bits (if any). The underflow bits are handled by aligning the first bit of the new data to overlap the last bit of the previous data then adding the new data to the old. If the last data written contained underflow bits, they will be represented by ones preceded by a zero in the position of the first non-matching bit. If the first bit of the new data is a one, all the underflow bits from the previous data will be changed to zeros and a one will be carried into the position held by the first non-matching bit. Enough output data must be buffered to propagate the carry to adjacent bytes if necessary.

Updating High and Low
When encoding, High and Low can each be updated without any other considerations. High and Low are shifted one bit less than the number of bits written because the first non-matching bit is also written to the output buffer. When updating Code while decoding, the highest bit must be inverted if the highest bit of Low is set after shifting. The highest bit of Low should not be cleared during decoding until first determining if the highest bit of Code should be inverted.

Mask Example
x = Bits to be written from Low

symbol 1           symbol 2
with underflow     without underflow
High  11001001...  11001001...
Low   11000111...  11000011...
mask  00000010...  00001010...
      xxxxxxx      xxxxx

Output Buffer Example

symbol 1    1100011
symbol 2          11000
buffer      11001001000