程式扎記: [ Data Structures with Java ] Section 23.1 : Bit Arrays

標籤

2011年4月20日 星期三

[ Data Structures with Java ] Section 23.1 : Bit Arrays

Preface : 
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 : 

* If either operand is of type long, the other is converted to long.
* If either operand is not of type long, both operands are converted to type int.

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 : 

- BitArray class partly implementation :
  1. public class BitArray {  
  2.     private int numberOfBits;  
  3.     private int byteArraySize;  
  4.     private byte[] member;  
  5.       
  6.     public BitArray(int numBits){  
  7.         numberOfBits = numBits;  
  8.         byteArraySize = (numberOfBits+7)/8;  
  9.         member = new byte[byteArraySize];  
  10.         for(int i=0; i< member.length; i++) member[i] = 0;  
  11.     }  
  12.     public BitArray(int[] b){  
  13.         numberOfBits = b.length;  
  14.         byteArraySize = (numberOfBits+7)/8;  
  15.         member = new byte[byteArraySize];  
  16.         for(int i=0; i< member.length; i++) member[i] = 0;  
  17.         for(int i=0; i
  18.     }  
  19. // Conversion from a primitive type :  
  20.     public void assignChar(char c){}  
  21.     public void assignInt(int n){}  
  22.   
  23. // Bit access and update :  
  24.     public int bit(int i){  
  25.         if(i<0 || i>=numberOfBits)  
  26.             throw new IndexOutOfBoundsException("BitArray bit() : bit out of range");  
  27.         if((member[arrayIndex(i)] & bitMask(i))!=0)  
  28.             return 1;  
  29.         else  
  30.             return 0;  
  31.     }  
  32.     public void set(int i){  
  33.           
  34.     }  
  35.   
  36. // Bit operations :  
  37.     public BitArray and(BitArray x){  
  38.         if(numberOfBits != x.numberOfBits)   
  39.             throw new IllegalArgumentException("BitArray : bit arrays are not the same size");  
  40.         BitArray tmp = new BitArray(numberOfBits);  
  41.         for(int i=0; i
  42.             tmp.member[i] = (byte)(member[i] & x.member[i]);  
  43.         return tmp;  
  44.     }  
  45.     public BitArray or(BitArray x){  
  46.         if(numberOfBits != x.numberOfBits)   
  47.             throw new IllegalArgumentException("BitArray : bit arrays are not the same size");  
  48.         BitArray tmp = new BitArray(numberOfBits);  
  49.         for(int i=0; i
  50.             tmp.member[i] = (byte)(member[i] | x.member[i]);  
  51.         return tmp;  
  52.     }  
  53.     public BitArray xor(BitArray x){  
  54.         if(numberOfBits != x.numberOfBits)   
  55.             throw new IllegalArgumentException("BitArray : bit arrays are not the same size");  
  56.         BitArray tmp = new BitArray(numberOfBits);  
  57.         for(int i=0; i
  58.             tmp.member[i] = (byte)(member[i] ^ x.member[i]);  
  59.         return tmp;  
  60.     }  
  61.     public BitArray not(){  
  62.         BitArray tmp = new BitArray(numberOfBits);  
  63.         for(int i=0; i
  64.             tmp.member[i] = (byte)(~member[i]);  
  65.         return tmp;  
  66.         }  
  67.     public BitArray shiftLeft(int n){         
  68.         int[] tmpBits = new int[numberOfBits];  
  69.         // fetch bit array  
  70.         for(int i=0; i
  71.             tmpBits[i] = bit(i);  
  72.             //System.out.println("bit["+i+"]="+bit(i));  
  73.         }  
  74.         for(int i=1; i
  75.             if((i+n)
  76.             else tmpBits[i] = 0;  
  77.         }  
  78.         return new BitArray(tmpBits);  
  79.     }  
  80.       
  81.     public BitArray shiftRight(int n){  
  82.         return shiftUnsignedRight(n);  
  83.     }  
  84.       
  85.     public BitArray shiftUnsignedRight(int n){  
  86.         int[] tmpBits = new int[numberOfBits];  
  87.         // fetch bit array  
  88.         for(int i=0; i
  89.         for(int i=numberOfBits-1; i>=0; i--) {  
  90.             if(i-n>=0) tmpBits[i] = tmpBits[i-n];  
  91.             else tmpBits[i] = 0;  
  92.         }  
  93.         return new BitArray(tmpBits);  
  94.     }  
  95.       
  96.     public BitArray shfitSignedRight(int n){  
  97.         int[] tmpBits = new int[numberOfBits];  
  98.         // fetch bit array  
  99.         for(int i=0; i
  100.         for(int i=numberOfBits-1; i>0; i--) {  
  101.             if(i-n>0) tmpBits[i] = tmpBits[i-n];  
  102.             else tmpBits[i] = 0;  
  103.         }  
  104.         return new BitArray(tmpBits);  
  105.     }  
  106.   
  107. // Input/Output :  
  108.     public void read(DataInputStream istr, int numBits){}  
  109.     public void write(DataOutputStream ostr){};  
  110.     @Override  
  111.     public String toString(){  
  112.         StringBuffer buffer = new StringBuffer("");  
  113.         for(int i=0; i
  114.             buffer.append(bit(i));  
  115.         return buffer.toString();  
  116.     }  
  117.   
  118. // Miscellaneous :  
  119.     public void clear(){}  
  120.     public void clear(int i){  
  121.         if(i<0 || i>=numberOfBits)  
  122.             throw new IndexOutOfBoundsException("BitArray clear() : bit out of range");  
  123.         member[arrayIndex(i)] &= ~bitMask(i);  
  124.     }  
  125.     public boolean equals(Object x){return false;}  
  126.     public int size(){return numberOfBits;}  

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 : 

- Method arrayIndex() :
  1. private int arrayIndex(int i){return i/8;}  

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 : 

- Method bitMask() :
  1. private byte bitMask(int i){return (byte)(  
  2.         // use & to find the remainder after dividing by 8;  
  3.         // remainder 0 puts a 1 in the left-most bit and 7 puts a 1 in the right-most bit  
  4.         1<<(7-(i&7)));  
  5. }  

 
- 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 ~. 

沒有留言:

張貼留言

網誌存檔