public class BitOutput extends Object
BitOutput
wraps an underlying output stream to
provide bitlevel output. Output is written through the method
writeBit(boolean)
, with true
used for the bit
1
and false
for the bit 0
.
The methods writeTrue()
and writeFalse()
are
shorthand for writeBit(true)
and
writeBit(false)
respectively.
If the number of bits written before closing the output does not
land on a byte boundary, the remaining fractional byte is filled
with 0
bits.
None of the methods in this class are safe for concurrent access by multiple threads.
Constructor and Description 

BitOutput(OutputStream out)
Construct a bit output wrapping the specified output stream.

Modifier and Type  Method and Description 

void 
close()
Closes underlying output stream and releases any resources
associated with the stream.

void 
flush()
Flushes writes to the underlying output stream.

static long 
leastSignificantBits(long n,
int numBits)
Returns the specified number of the least significant bits of
the specified long value as a long.

static int 
mostSignificantPowerOfTwo(long n)
Returns the index of the most significant bit filled for the
specified long value.

static long 
sliceBits(long n,
int leastSignificantBit,
int numBits)
Returns a slice of bits in the specified long value running
from the specified least significant bit for the specified
number of bits.

void 
writeBinary(long n,
int numBits)
Writes the bits of a binary representation of the specified
nonnegative number in the specified number of bits.

void 
writeBit(boolean bit)
Writes the specified bit.

void 
writeDelta(long n)
Writes the bits for the Elias delta code for the specified
positive number.

void 
writeFalse()
Writes a single
false (0 ) bit. 
void 
writeFibonacci(long n)
Writes the Fibonacci code for the specified positive number.

void 
writeGamma(long n)
Writes the bits for the Elias gamma code for the specified
positive number.

void 
writeRice(long n,
int numFixedBits)
Writes the bits for Rice code for the specified nonnegative
number with the specified number of bits fixed for the binary
remainder.

void 
writeTrue()
Writes a single
true (1 ) bit. 
void 
writeUnary(int n)
Writes the bits for a unary code for the specified positive
number.

public BitOutput(OutputStream out)
out
 Underlying output stream.public void writeUnary(int n) throws IOException
n
is
defined by:
unaryCode(n) = 0^{n1} 1
In words, the number n
is coded as
n1
zeros followed by a one. The following
table illustrates the first few unary codes:
Number Code 1 1
2 01
3 001
4 0001
5 00001
n
 Number to code.IOException
 If there is an I/O error writing
to the underlying output stream.IllegalArgumentException
 If the number to be encoded is
zero or negative.public void writeBinary(long n, int numBits) throws IOException
For instance, the following illustrates one, two and threebit codings.
Number Binary Code for Num Bits 1 2 3 0 1 0 00 000 1 1 1 01 001 2 10 Exception
10 010 3 10 Exception
11 011 4 100 Exception
Exception
100 5 101 Exception
Exception
101 6 110 Exception
Exception
110 7 111 Exception
Exception
111 8 1000 Exception
Exception
Exception
n
 Number to code.numBits
 Number of bits to use for coding.IllegalArgumentException
 If the number to code is
negative, the number of bits is greater than 63, or the number
will not fit into the specified number of bits.IOException
 If there is an error writing to the
underlying output stream.public void writeRice(long n, int numFixedBits) throws IOException
both of which are defined by shifting, and then coding each in turn using a unary code for the quotient and binary code for the remainder:
m = 2^{b} = (1<<b) q = (n  1) / m = (n  1) >>> b r = n  q*m  1 = n  (q << b)  1
riceCode(n,b) = unaryCode(q) binaryCode(r)
For example, we get the following codes with the number of
fixed remainder bits set to 1, 2 and 3, with the unary coded
quotient separated from the binary coded remainder by a space:
In the limit, if the number of remaining bits to code is set to zero, the Rice code would reduce to a unary code:
Number n
Binary Code for Number of Remainder Bits b=1 b=2 b=3 1 1 1 0 1 00 1 000 2 10 1 1 1 01 1 001 3 11 01 0 1 10 1 010 4 100 01 1 1 11 1 011 5 101 001 0 01 00 1 100 6 110 001 1 01 01 1 101 7 111 0001 0 01 10 1 110 8 1000 0001 1 01 11 1 111 9 1001 00001 0 001 00 01 000 10 1010 00001 1 001 01 01 001 11 1011 000001 0 001 10 01 010 12 1100 000001 1 001 11 01 011 13 1101 0000001 0 0001 00 01 100 14 1110 0000001 1 0001 01 01 101 15 1111 00000001 0 0001 10 01 110 16 10000 00000001 1 0001 11 01 111 17 10001 000000001 0 00001 00 001 000
riceCode(n,0) = unaryCode(n)
but this method will throw an exception with a remainder size
of zero.
In the limit the other way, if the number of remaining bits is set to the width of the maximum value, the Rice code is just the unary coding of 1, which is the single binary digit 1, followed by the binary code itself:
riceCode(n,64) = unaryCode(1) binaryCode(n,64) = 1 binaryCode(n,64)
The method will throw an exception if the encoding produces a unary code that would output more bits than would fit in a positive integer (that is, more than (2^{32}1) bits. For more information, see:
n
 Number to code.numFixedBits
 Number of bits to use for the fixed
remainder encoding.IOException
 If there is an error writing to the
underlying output stream.IllegalArgumentException
 If the number to be encoded is
not positive, if the number of fixed bits is not positive, or if
the unary prefix code overflows.public void writeFibonacci(long n) throws IOException
Fibonacci numbers are defined by setting
The first few Fibonacci numbers are:Fib(0) = 0 Fib(1) = 1 Fib(n+2) = Fib(n+1) + Fib(n)
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
This method starts with the second 1
value,
namely Fib(2)
, making the sequence a sequence
of unique numbers starting with 1, 2, 3, 5,...
.
The Fibonacci representation of a number is a bit vector indicating the Fibonacci numbers used in the sum. The Fibonacci code reverses the Fibonacci representation and appends a 1 bit. Here are examples for the first 17 numbers:
For example, the number 11 is coded as the sum of the nonconsecutive Fibonacci numbers 8 + 3, so the Fibonacci representation is
Number Fibonacci Representation Fibonacci Code 1 1 11 2 10 01 1 3 100 001 1 4 101 101 1 5 1000 0001 1 6 1001 1001 1 7 1010 0101 1 8 10000 00001 1 9 10001 10001 1 10 10010 01001 1 11 10100 00101 1 12 10101 10101 1 13 100000 000001 1 14 100001 100001 1 15 100010 010001 1 16 100100 001001 1 17 100101 101001 1
10100
(8 is the fifth number in
the series above, 3 is the third). Its Fibonacci code reverses
the number to 00101
and appends a 1
to yield 001011
.
Fibonacci codes can represent arbitrary positive numbers up
to Long.MAX_VALUE
.
See Math.FIBONACCI_SEQUENCE
for a definition of
the Fibonacci sequence as an array of longs.
In the limit (for larger numbers), the number of bits used by a Fibonacci coding is roughly 60 percent higher than the number of bits used for a binary code. The benefit is that Fibonacci codes are prefix codes, whereas binary codes are not.
n
 Number to encode.IllegalArgumentException
 If the number is not positive.IOException
 If there is an I/O exception writing to the
underlying stream.public void writeGamma(long n) throws IOException
n
is based on its binary representation b[k1],...,b[0]
:
gammaCode(b[k1],...,b[0]) = unaryCode(k),b[k1],...,b[0]
In words, the position of the most significant binary digit is
coded using a unary code, with the remaining digits making up
the rest of the gamma code.
The Following table provides an illustration of the gamma coding of the first 17 positive integers. Each row displays the number being coded, its binary representation, and its gamma code. The gamma code is displayed as its unary coding of the number of digits in the binary representation followed by a space and then by the digits of the binary representation after the first one.
For more information on gamma coding, see:
Number Binary Gamma code 1 1 1 2 10 01 0 3 11 01 1 4 100 001 00 5 101 001 01 6 110 001 10 7 111 001 11 8 1000 0001 000 9 1001 0001 001 10 1010 0001 010 11 1011 0001 011 12 1100 0001 100 13 1101 0001 101 14 1110 0001 110 15 1111 0001 111 16 10000 00001 0000 17 10001 00001 0001
n
 Number to code.IOException
 If there is an I/O error writing to the
underlying stream.IllegalArgumentException
 If the number to be encoded is
zero or negative.public void writeDelta(long n) throws IOException
n
is based on its binary representation
b[k1],...,b[0]
:
deltaCode(b[k1],...,b[0]) = gammaCode(k),b[k1],...,b[0]
In words, the position of the most significant binary digit is
coded using a gamma code, with the remaining digits making up
the rest of the gamma code.
The following table illustrates the delta codes for some small numbers. Each row lists the number, its binary representation, and its delta code. The delta code is written as the initial gamma code of its most significant digit's position and the remaining bits in the binary representation. Note that the delta codes are longer for small numbers, but shorter for large numbers.
For more information on delta coding, see:
Number Binary Delta code 1 1 1 2 10 010 0 3 11 010 1 4 100 011 00 5 101 011 01 6 110 011 10 7 111 011 11 8 1000 00100 000 9 1001 00100 001 10 1010 00100 010 11 1011 00100 011 12 1100 00100 100 13 1101 00100 101 14 1110 00100 110 15 1111 00100 111 16 10000 00101 0000 17 10001 00101 0001
n
 Number to code.IOException
 If there is an I/O error writing to the
underlying stream.IllegalArgumentException
 If the number to be encoded is
zero or negative.public void close() throws IOException
0
.
The close method calls the OutputStream.close()
method on the contained output stream.
IOException
 If there is an I/O exception writing the
next byte or closing the underlying output stream.public void flush() throws IOException
0
. It then calls OutputStream.flush()
on
the underlying output stream.IOException
 If there is an exception writing to or
flushing the underlying output stream.public void writeBit(boolean bit) throws IOException
true
is
used for the bit 1
and false
for
0
.bit
 Value to write.IOException
 If there is an exception writing to the
underlying output stream.public void writeTrue() throws IOException
true
(1
) bit.IOException
 If there is an exception writing to the
underlying output stream.public void writeFalse() throws IOException
false
(0
) bit.IOException
 If there is an exception writing to the
underlying output stream.public static long leastSignificantBits(long n, int numBits)
leastSignificantBits(13,2) = 3
, because 13 is
1011
in binary and the two least significant
digits are 11
.n
 Value whose least significant bits are returned.numBits
 The number of bits to return.IllegalArgumentException
 If the number of bits is less than
1 or greater than 64.public static long sliceBits(long n, int leastSignificantBit, int numBits)
110
,
the bit indexed 0 is 0, the bit indexed 1 is 1 and the bit
indexed 2 is 1. For example, sliceBits(57,2,3) =
6
, because 57 is 111001
in binary and the
three bits extending to the left from position 2 are
110
, which is 2.n
 Value to be sliced.leastSignificantBit
 Index of least significant bit in
the result.numBits
 Number of bits including least significant bit
to return.IllegalArgumentException
 If the number of bits is less
than zero or greater than 64, or if the least significant bit
index is less than 0 or greater than 63.public static int mostSignificantPowerOfTwo(long n)
mostSignificantPowerOfTwo(1) = 0 mostSignificantPowerOfTwo(2) = 1 mostSignificantPowerOfTwo(4) = 2 mostSignificantPowerOfTwo(8) = 3
This result of this method may be defined in terms of
the builtin method Long.numberOfLeadingZeros(long)
, added
in Java 1.5, by:
mostSignificantPowerOfTwo(n) = Math.max(0,63Long.numberOfLeadingZeros(n))
n
 The specified value.