Applications such as compiler code generation and compression algorithms create data that includes specific sequences of bits. For instance, the machine code for an addition instruction is ofter a specific sequence of 16 bits. Certain bits have fixed values, but others belong to bit fields that indicate the size of data, the source and the destination of the data for the operation.
Java allows manipulation of individual bits with the operators OR("|"), AND("&"), NOT("~"), and XOR("^"). The operators take operands of type int, long, short, byte and char. A short is a 16 bit integer in the range from -32768 to 32767, and a byte is an 8-bit integer value in the range from -128 to 127. Table below defines the operators :
Binary Numeric Promotion :
Before performing the bitwise operator |, &, or ^, Java performs binary numeric promotion on the operands. The type of the bitwise operator expression is the promoted type of the operands. The rules of promotion are as follows :
In this case of the unary operator ~, Java converts a byte, char or a short to int before applying the operator, and the resulting value is an int.
The BitArray Class :
Rather than requiring a programmer to use low-level bit operations, we develop the BitArray class as an alternative. A BitArray object treats a sequence of nbits as an array, with bit 0 the first bit on the left, bit 1 the second bit and n-1 the last bit on the right. For instance, if we use a bit array to represent the 5 bit stream 10111, bit 0 is 1, bit 1 is 0 and bit 2 through 4 are 1. To be effective, a bit array must supply operations that return the value of a particular bit in the bit stream and that set and clear individual bits. In addition, the class should provide methods that implement a set of bit-handling operations.
The first constructor creates a bit array all of whose bits are 0. The second constructor simplifies the creation of short bit vectors by using a Java integer array containing the values 1 and 0 to initialize the individual bits. Three methods, assignInt(), assingChar(), and assignByte(), allow a convenient conversion between an integer, a character or a byte and the corresponding bit array. The methods read() and write() implement I/O for a binary stream. We discuss binary streams in Section 23.2. The class has the toString() method, which returns a binary string representation of the bits in the array. The following is a skeletal listing of the class that includes private data members and constructions. The other methods are grouped into categories and displayed after the class listing :
Implementing the BitArray Class :
The BitArray class uses Java bit operations on individual bits in a byte to efficiently implement a BitArray object. An array of byte type stores the range of individual bits with numbers 0 to numberOfBits-1. The implementation views the array, called member, as a stream of bits. The element member[0] provides 8 bits, member[1] provides 8 more bits and so forth. There is a mapping from a bit in member to a bit number in the range 0 ... numberOfBits-1. The left-most bit of member[0] represents bits 0 and the right most bit of member[0] represents bit 7. We continue with the left-most bit of member[1] representing bit 8, and so forth. The following illustrates the storage scheme :
The private methods arrayIndex() and bitMask() implement the storage scheme. The method arrayIndex() determines the array element to which bit ibelongs. Simply divide i by 8. In this way, i=0 through i=7 belongs to member[0], i=8 through i-15 belongs to member[1] and so forth :
After locating the correct array index, apply the method bitMask() that returns a byte value containing a 1 in the bit position representing i. This value, called a mask, can be used to set or clear the bit :
- The BitArray Constructors
There are two constructors that create a BitArray object. One creates an empty bit array of a specified size; the second constructor initializes the bit array by using a Java integer array of 0 and 1 values. Build an empty bit array by determining the number of byte array elements needed to represent the range of bit numbers, allocate the array member to have the number of elements, and fill the array with 0 values.
- BitArray Operators
The class implements the bitwise operators or() ,and() ,xor() and not(), as well as the left/rigth shift operators. For instance, to implement the bitwise or() method, construct a BitArray object, tmp, of the same size as the number of bits in the current object and x. Assign its elements to be bitwise OR of the array element representing the current object and x. Return this new bit array as the value of the method. Note that the method throws the IllegalArgumentException if the current object and x do not have the same size :
- Bit Access and Modification Methods :
Methods such as bit() and clear() access individual bits by applying the private method arrayIndex() and bitMask(). The method bit() returns 1 if it finds a 1 in the bit corresponding to i, 0 if it does not.
The method clear() turns off the bit corresponding to i. The process uses the AND operator and a mask that contains all 1s except for the specific i bit. Create the mask by using the bitwise NOT operator ~.
沒有留言:
張貼留言