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

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

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

c = 234;

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

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

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

1. /*createdbychicochen
2. *date2008/10/25
3. */
4. #ifndef_BIT_VECTOR_
5. #define_BIT_VECTOR_
6. #include<iostream>
7. usingnamespacestd;
10. classBITVector
11. {
12. private:
13. __int64*bitarray;
14. constintbits;
15. constunsigned__int64mask;
16. intsize;
17. voidSetOne(intindex);//xis0
18. voidSetZero(intindex);//xis1
19. voidLarger();
21. public:
22. BITVector(void);
23. voidSet(intindex,intx);//xis0or1
24. intGet(intindex);
25. intSize();
26. voidSetInt(unsignedintinteger,intstart,intlen);
27. voidPrintfZeroOne(intstart,intlen);//printtheunsigneditas0or1
28. voidSetBitVector(BITVector&c,intstart,intlen);
29. constBITVector&operator=(constBITVector&bitVector);
30. explicitBITVector(constBITVector&bitVector);
32. public:
33. ~BITVector(void);
34. };
35. #endif

然后是bitVector.cpp文件

1. /*createdbychicochen
2. *date2008/10/25
3. */
4. #include"StdAfx.h"
5. #include"BITVector.h"
7. BITVector::BITVector(void):mask(0x8000000000000000),bits(sizeof(__int64)*8)
8. {
9. bitarray=new__int64[1];
10. memset(bitarray,0,sizeof(__int64));
11. size=1;
12. }
14. BITVector::~BITVector(void)
15. {
16. size=0;
17. delete[]bitarray;
18. }
20. voidBITVector::Set(intindex,intx)
21. {
22. if(x==0)
23. {
24. returnSetZero(index);
25. }
26. else
27. {
28. returnSetOne(index);
29. }
30. }
32. voidBITVector::SetZero(intindex)
33. {
34. intinnIndex=index/bits;
35. intbitPos=index&(bits-1);//innIndex%8
36. if(innIndex<size)
37. {
38. //vectormaybehasenoughspacetostorethis.
39. this->bitarray[innIndex]=this->bitarray[innIndex]&~(mask>>bitPos);
40. }
41. elseif(innIndex==size)
42. {
43. //shouldlargerthesizeofbitarray
44. //andinnIndexmustbethefirstbitoflastchar
46. if(bitPos==0)
47. {
48. //correct
49. this->Larger();
50. this->bitarray[innIndex]=this->bitarray[innIndex]&~(mask>>bitPos);
52. }
53. else
54. {
55. //error
57. }
58. }
59. else
60. {
61. //theremaybesomethingerror,orsomecodemissing
63. }
64. }
67. voidBITVector::Larger()
68. {
69. __int64*tempArray=new__int64[size];
70. memcpy(tempArray,this->bitarray,sizeof(__int64)*size);
71. delete[]this->bitarray;
73. this->bitarray=new__int64[size*2];//maybeerror
74. memset(bitarray,0,sizeof(__int64)*size*2);
75. memcpy(this->bitarray,tempArray,sizeof(__int64)*size);
76. size=size*2;
77. delete[]tempArray;
80. }
82. voidBITVector::SetOne(intindex)
83. {
84. intinnIndex=index/bits;//youcanuse>>(bits-1)
85. intbitPos=index%bits;//innIndex&(bits-1)
86. if(innIndex<size)
87. {
88. //vectormaybehasenoughspacetostorethis.
89. this->bitarray[innIndex]=this->bitarray[innIndex]|(mask>>bitPos);
90. }
91. elseif(innIndex==size)
92. {
93. //shouldlargerthesizeofbitarray
94. //andinnIndexmustbethefirstbitoflastchar
96. if(bitPos==0)
97. {
98. //correct
99. this->Larger();
100. this->bitarray[innIndex]=this->bitarray[innIndex]|(mask>>bitPos);
102. }
103. else
104. {
105. //error
107. }
108. }
109. else
110. {
111. //theremaybesomethingerror,orsomecodemissing
113. }
115. }
117. intBITVector::Get(intindex)
118. {
119. if(index<size*bits)
120. {
121. intposition=index&(bits-1);//%bits
122. intinnIndex=index/bits;
123. __int64i=this->bitarray[innIndex]&(mask>>position);
124. if(i==0)
125. {
126. return0;
127. }
128. else
129. {
130. return1;
131. }
132. }
133. throw"accessoutofthearray";
134. }
136. intBITVector::Size()
137. {
138. returnsize*bits;
139. }
141. //intintegeris0x01010111
142. //startisthestartpositionofbitvector,andstartstartszero
143. //lenislengthofthenumberofbitsyouwantsetintobitarray
144. voidBITVector::SetInt(unsignedintinteger,intstart,intlen)
145. {
146. intfinalPos=start+len;
147. inti=start;
148. intj=0;
149. inttemp=0;
150. for(;i<finalPos;i++,j++)
151. {
152. temp=integer&(0x80000000>>j);
153. this->Set(i,temp);
154. }
155. }
158. voidBITVector::PrintfZeroOne(intstart,intlen)
159. {
160. intfinalPos=start+len;
161. inttemp=0;
162. for(inti=start;i<finalPos;i++)
163. {
164. printf("%d",this->Get(i));
165. }
166. }
168. //startiswheretoinsertbitvectorc
169. //lenisthelengthofbitsinserted
170. //"start"isofthis,and"len"isofc;
171. voidBITVector::SetBitVector(BITVector&c,intstart,intlen)
172. {
174. for(inti=0;i<len;i++)
175. {
176. this->Set(start+i,c.Get(i));
177. }
179. }
181. //copyconstruct
182. BITVector::BITVector(constBITVector&bitVector):mask(0x8000000000000000),bits(sizeof(__int64)*8)
183. {
184. this->size=bitVector.size;
185. this->bitarray=new__int64[this->size];
186. memcpy(this->bitarray,bitVector.bitarray,sizeof(__int64)*bitVector.size);
187. }
189. constBITVector&BITVector::operator=(constBITVector&bitVector)
190. {
191. if(this!=&bitVector)
192. {
193. this->size=bitVector.size;
194. delete[]this->bitarray;
195. this->bitarray=new__int64[this->size];
196. memcpy(this->bitarray,bitVector.bitarray,sizeof(__int64)*this->size);
197. }
198. return*this;
199. }