编程练习——可变长bit数组(bitArray)

其实c++里有bitset这个类，但是bitset使用时必须给定大小。例如

bitset<8> c;//这里必须在编码里写死，不能使用变量替代

c = 234;

我主要是用这个东西来存储可变长的huffman编码。所以这个类对我根本不能用。除非开始就给一个足够大的bitset。

所以我创建里一个可变长的bit vector用于存放Huffman编码。

在这里内部使用的是__int64,64位。当然根据实际需要可以将这个做为模板传入，不过现在还没有这样编码。

1. /* created by chico chen
2. *  date 2008/10/25
3. */
4. #ifndef BIT_VECTOR
5. #define BIT_VECTOR
6. #include 
7. using namespace std;
8. 9. 10. class BITVector
9. {
10. private :
11. __int64 * bitarray;
12. const int bits;
13. const unsigned __int64 mask ;
14. int size;
15. void SetOne( int index); // x is 0
16. void SetZero( int index); // x is 1
17. void Larger();
18. 21. public :
19. BITVector( void );
20. void Set( int index, int x); // x is 0 or 1
21. int Get( int index);
22. int Size();
23. void SetInt(unsigned int integer, int start, int len);
24. void PrintfZeroOne( int start , int len); // print the unsigned it as 0 or 1
25. void SetBitVector(BITVector & c, int start, int len);
26. const BITVector& operator=( const BITVector& bitVector);
27. explicit BITVector( const BITVector & bitVector);
28. 32. public :
29. ~BITVector( void );
30. };
31. #endif

然后是bitVector.cpp文件

1. /* created by chico chen
2. *  date 2008/10/25
3. */
4. #include “StdAfx.h”
5. #include “BITVector.h”
6. 7. BITVector::BITVector( void ):mask(0x8000000000000000),bits( sizeof ( __int64 )*8)
7. {
8. bitarray = new __int64 [1];
9. memset(bitarray,0, sizeof ( __int64 ));
10. size = 1;
11. }
12. 14. BITVector::~BITVector( void )
13. {
14. size = 0;
15. delete [] bitarray;
16. }
17. 20. void BITVector::Set( int index, int x)
18. {
19. if (x == 0)
20. {
21. return SetZero(index);
22. }
23. else
24. {
25. return SetOne(index);
26. }
27. }
28. 32. void BITVector::SetZero( int index)
29. {
30. int innIndex = index/bits;
31. int bitPos = index & (bits-1); // innIndex % 8
32. if ( innIndex < size)
33. {
34. // vector maybe has enough space to store this .
35. this ->bitarray[innIndex] = this ->bitarray[innIndex] & ~(mask >> bitPos);
36. }
37. else if (innIndex == size)
38. {
39. // should larger the size of bitarray
40. // and innIndex must be the first bit of last char
41. 46. if (bitPos == 0)
42. {
43. // correct
44. this ->Larger();
45. this ->bitarray[innIndex] = this ->bitarray[innIndex] & ~(mask >> bitPos);
46. 52. }
47. else
48. {
49. // error
50. 57. }
51. }
52. else
53. {
54. // there may be something error, or some code missing
55. 63. }
56. }
57. 66. 67. void BITVector::Larger()
58. {
59. __int64 * tempArray = new __int64 [size];
60. memcpy(tempArray, this ->bitarray, sizeof ( __int64 )*size);
61. delete [] this ->bitarray;
62. 73. this ->bitarray = new __int64 [size*2]; // may be error
63. memset(bitarray,0, sizeof ( __int64 )size2);
64. memcpy( this ->bitarray,tempArray, sizeof ( __int64 )*size);
65. size = size*2;
66. delete [] tempArray;
67. 79. 80. }
68. 82. void BITVector::SetOne( int index)
69. {
70. int innIndex = index/bits; // you can use >>(bits-1)
71. int bitPos = index % bits; // innIndex & (bits-1)
72. if ( innIndex < size)
73. {
74. // vector maybe has enough space to store this .
75. this ->bitarray[innIndex] = this ->bitarray[innIndex] | (mask >> bitPos);
76. }
77. else if (innIndex == size)
78. {
79. // should larger the size of bitarray
80. // and innIndex must be the first bit of last char
81. 96. if (bitPos == 0)
82. {
83. // correct
84. this ->Larger();
85. this ->bitarray[innIndex] = this ->bitarray[innIndex] | (mask >> bitPos);
86. 102. }
87. else
88. {
89. // error
90. 107. }
91. }
92. else
93. {
94. // there may be something error, or some code missing
95. 113. }
96. 115. }
97. 117. int BITVector::Get( int index)
98. {
99. if (index < size*bits)
100. {
101. int position = index & (bits-1); // % bits
102. int innIndex = index/bits;
103. __int64 i = this ->bitarray[innIndex] & (mask >> position);
104. if (i == 0)
105. {
106. return 0;
107. }
108. else
109. {
110. return 1;
111. }
112. }
113. throw “access out of the array” ;
114. }
115. 136. int BITVector::Size()
116. {
117. return size*bits;
118. }
119. 141. // int integer is 0x01010111
120. // start is the start position of bitvector, and start starts zero
121. // len is length of the number of bits you want set into bit array
122. void BITVector::SetInt(unsigned int integer, int start, int len)
123. {
124. int finalPos = start + len;
125. int i=start;
126. int j = 0;
127. int temp = 0;
128. for (;i < finalPos; i++,j++)
129. {
130. temp = integer & (0x80000000 >> j);
131. this ->Set(i,temp);
132. }
133. }
134. 157. 158. void BITVector::PrintfZeroOne( int start, int len)
135. {
136. int finalPos = start+len;
137. int temp = 0;
138. for ( int i = start; i < finalPos; i++)
139. {
140. printf( “%d” , this ->Get(i));
141. }
142. }
143. 168. // start is where to insert bit vector c
144. // len is the length of bits inserted
145. // “start” is of this, and “len” is of c;
146. void BITVector::SetBitVector(BITVector & c, int start, int len)
147. {
148. 174. for ( int i = 0; i < len; i++)
149. {
150. this ->Set(start+i,c.Get(i));
151. }
152. 179. }
153. 181. // copy construct
154. BITVector::BITVector( const BITVector & bitVector):mask(0x8000000000000000),bits( sizeof ( __int64 )*8)
155. {
156. this ->size = bitVector.size;
157. this ->bitarray = new __int64 [ this ->size];
158. memcpy( this ->bitarray,bitVector.bitarray, sizeof ( __int64 )*bitVector.size);
159. }
160. 189. const BITVector& BITVector::operator=( const BITVector& bitVector)
161. {
162. if ( this != &bitVector)
163. {
164. this ->size = bitVector.size;
165. delete [] this ->bitarray;
166. this ->bitarray = new __int64 [ this ->size];
167. memcpy( this ->bitarray,bitVector.bitarray, sizeof ( __int64 )* this ->size);
168. }
169. return * this ;
170. }