本来仅仅只是用来做哈夫曼实验时的辅助，后来一想干脆封装好，省得以后又要用到比特位的操作。
基本用法示例:
1 BitArray bits; 2 bits[ 0] = 0; 3 bits[ 1] = 1; 4 cout<<bits[ 0]<<endl; // 输出0 5 cout<<bits[ 1]<<endl; // 输出1 6 cout<<bits[ 2]<<endl; // 抛出越界异常
BitArray有四个成员变量：
uchar * m_data; // 字符指针
size_t m_bitsLength; // 数组长度，单位是：比特
size_t m_bitsCapacity;// 数组容量，单位是：比特，这个最终保存都是8的倍数
bool m_owns; // 是否拥有对m_data的控制权，有的话在析构时会释放空间
主要的构造函数有：
BitArray(); // 默认的，会创建一个10字节，容量为80，长度为0的比特数组
BitArray(size_t bitsLength,size_t bitsCapacity=0U); // 创建一个初始长度为bitsLength的比特数组
BitArray(uchar* data,int bitsLength,bool isClear=false ,bool isOwns=true);
// 这一个构造函数会将data视作数据源，isClear表示是否进行清零，isOwns表示是否获得控制权。
主要的函数：
bool set(int position,bool bit,bool isAllowOutOfRange=false,bool isAllowOutofSize=true,bool isAllowToInfinite=false);
这一个函数参数有点长，比如 set(0,1) 表示将第0个比特位设置为1。如果你需要访问的位置超出了目前比特数组的长度，那么就需要将isAllowOutOfRange设置为true。但是此时的位置还是不能超过目前容量的三倍。 如果有这个需要，可以访问 set(pos,1,true,true,true); 实际上最后一个参数为true时，就相当于屏蔽第三个和第四个参数了。
总之如果需要比特数组进行缓慢的扩张时，仅仅使用 set(pos,1,true) 形式即可，每次达到容量限制后，就会扩容1.5倍，这个参数可以修改。
bool get(int position);
访问position位置的真值，position不能大于等于目前的长度，否则会抛出异常
另外还实现了一个 at() 函数 和 [] 操作符
Bit operator[](int position);
Bit at( int position);当你使用 bits[pos]=1 时，调用了set函数，设置是允许进行不超过三倍的扩增，具体实现依赖于Bit类。
因为如果需要对其进行赋值，必须是左值，显然一个比特位是没办法成为左值的，所以我才 用了一个 Bit 类来实现这种需求。
如果需要将最终的结果输出，可以按照下面代码所做：
BitArray bits; // ........ // ........ unsigned char * t_data = bits.getData(); size_t t_len = bits.getByteSize(); // t_len 就是最后的长度了，最好用 getBitSize()得到有效的比特长度
其他就是一些对大小和容量进行访问控制的函数了，慢慢的看吧。
1 #ifndef __WH_BITARRAY_H_ 2 #define __WH_BITARRAY_H_ 3 4 /* * 5 在map的position位置写入bit 6 * */ 7 bool writeBit(unsigned char *, int, bool); 8 9 /* * 10 读取map的position位置的bit数据 11 * */ 12 bool readBit(unsigned char *, int); 13 14 /* 三个用于 BitArray 的静态常量 */ 15 static const size_t c_initBitsCapacity = 80U; 16 static const double c_increaseCapacity = 1.5; 17 static const double c_maxAllowedOutOfBound = 3.0; 18 19 class BitArray; 20 21 class Bit{ 22 private: 23 BitArray * m_bits; 24 int m_position; 25 public: 26 Bit():m_bits(nullptr),m_position( 0){} 27 Bit(BitArray *bits, int position); 28 Bit& operator =( bool bit); 29 operator bool(); 30 }; 31 32 /* * 33 BitArray 可以对比特位进行直接操作，通过构造方法或者setData()传入一个字符指针之后就可以将BitArray视作一个由比特组成的数组 34 set() 以及 get() 方法封装了对位进行操作的两个最主要的函数 35 * */ 36 class BitArray{ 37 // 类型，常量定义区 38 /* 无符号字符类型 */ 39 typedef unsigned char uchar; 40 inline size_t BitsToBytes(size_t bits){ return (bits- 1)/ 8+ 1;} 41 inline size_t BytesToBits(size_t bytes){ return 8*bytes;} 42 public: 43 /* * 44 默认构造函数，创建一个默认大小 c_initBitsCapacity 的比特数组 45 * */ 46 BitArray(); 47 BitArray& operator =( const BitArray& bits); 48 BitArray& operator =(BitArray&& bits); 49 BitArray( const BitArray& bits); 50 BitArray(BitArray&& bits); 51 /* * 52 创建一个长为bitsLength，最大容量为bitsCapacity的比特数组 53 * */ 54 BitArray(size_t bitsLength,size_t bitsCapacity= 0U); 55 /* * 56 根据现有字符数组创建一个比特数组 57 data: 现有的字符数组 58 bitsLength: 该字符数组有效的比特位长度，创建之后的最大容量为 8*((bitsLength-1)/8+1) 59 isClear: 该字符数组是否进行清零 60 isOwns: 是否允许比特数组获得对该字符数组的控制权，若为true则在析构或其他恰当时机将会进行内存释放 61 * */ 62 BitArray(uchar* data, int bitsLength, bool isClear= false , bool isOwns= true); 63 ~BitArray(); 64 bool operator==(BitArray &bits); 65 /* * 66 获得position位置的真值， 67 * */ 68 Bit operator[]( int position){ return Bit( this,position);} 69 Bit at( int position){ return Bit( this,position);} 70 /* * 71 获得position位置的真值，有效范围为 [-(int)getBitSize(),getBitSize()),超出将抛出异常 72 * */ 73 bool get( int position); 74 /* * 75 获得比特数组的底层字节数据，该数组的有效长度可由 getBitSize()/getByteSize() 得到 76 * */ 77 uchar* getData(){ return m_data;} 78 /* * 79 根据现有字符数组更新比特数组，原有的数据将根据m_owns的真值来决定是否释放 80 data: 现有的字符数组 81 bitsLength: 该字符数组有效的比特位长度，创建之后的最大容量为 8*((bitsLength-1)/8+1) 82 isClear: 该字符数组是否进行清零 83 isOwns: 是否允许比特数组获得对该字符数组的控制权，若为true则在析构或其他恰当时机将会进行内存释放 84 * */ 85 void setData(uchar *data, int bitsLength, bool isClear= false, bool isOwns= true); 86 /* * 87 对比特数组的position位置进行数据更新 88 position: 访问位置，以0为起点，合法范围为 [-(int)getBitSize(),getBitSize())，超出将可能抛出异常 89 bit: 将要更新的真值 90 isAllowOutOfRange: 是否允许在适当时机进行数据扩增，并且最大扩充倍数为c_maxAllowOutOfRange，默认是不允许的 91 isAllowOutOfSize: 是否允许当超出当前长度，但是并未超出容量时进行自动扩张,默认是允许的 92 isAllowToInfinite： 是否允许大小无限大，默认是不允许的 93 * */ 94 bool set( int position, bool bit, bool isAllowOutOfRange= false, bool isAllowOutofSize= true, bool isAllowToInfinite= false); 95 /* * 96 设置比特数组的有效长度，单位：比特 97 如果超出容量，将会进行扩容，扩增后的容量为 c_increaseCapacity*newBitsLength 98 * */ 99 size_t setBitSize(size_t newBitsLength); 100 /* * 101 设置比特数组的最大容量，单位：比特，但是将会以8为基本单位对齐 102 只要底层数据的字节数与新容量的占用字节数不同，就将重新分配内存，并且获得对新内存的支配权 103 * */ 104 size_t setBitCapacity(size_t newBitsCapacity); 105 /* * 106 获得比特数组的有效比特长度，单位为：比特 107 * */ 108 size_t getBitSize(){ return m_bitsLength;} 109 /* * 110 获得比特数组的最大比特容量，单位为：比特 111 * */ 112 size_t getBitCapacity(){ return m_bitsCapacity;} 113 /* * 114 获得比特数组的有效字节长度，单位为：字节 115 * */ 116 size_t getByteSize(){ return BitsToBytes(m_bitsLength);} 117 /* * 118 获得比特数组的最大字节容量，单位为：字节 119 * */ 120 size_t getByteCapacity(){ return BitsToBytes(m_bitsCapacity);} 121 /* * 122 判断是否拥有对底层数组的控制权 123 * */ 124 bool isOwns(){ return m_owns;} 125 /* * 126 设置是否拥有对底层数组的控制权 127 * */ 128 bool setOwns( bool owns); 129 private: 130 /* 底层数据数组 */ 131 uchar * m_data; 132 /* 比特数组的有效长度 */ 133 size_t m_bitsLength; 134 /* 比特数组的最大比特位容量，该值将永远是8的倍数 */ 135 size_t m_bitsCapacity; 136 /* 代表比特数组是否拥有对m_data的控制权，拥有控制权则将在适当时机对其进行释放 */ 137 bool m_owns; 138 }; 139 #endif
1 #include "BitArray.h"
2 #include < string.h> 3 #include <exception> 4 #include <stdexcept> 5 6 BitArray::BitArray() 7 { 8 m_owns = true; 9 m_bitsLength = 0; 10 if(c_initBitsCapacity == 0){ 11 m_data = nullptr; 12 m_bitsCapacity = 0; 13 } else{ 14 size_t t_bytesLength = BitsToBytes(c_initBitsCapacity); 15 m_data = new uchar[t_bytesLength]; 16 memset(m_data, 0,t_bytesLength); 17 if(!m_data){ 18 // 内存分配失败逻辑 19 throw std::bad_alloc(); // ("can't allow memory!"); 20 } 21 m_bitsCapacity = 8*t_bytesLength; 22 } 23 } 24 25 BitArray::BitArray(BitArray&& bits) 26 { 27 m_data = bits.m_data; 28 m_owns = true; 29 m_bitsCapacity = bits.m_bitsCapacity; 30 m_bitsLength = bits.m_bitsLength; 31 bits.m_owns = false; 32 bits.m_data = nullptr; 33 } 34 35 BitArray::BitArray( const BitArray& bits) 36 { 37 * this = bits; 38 } 39 40 BitArray& BitArray:: operator =( const BitArray& bits) 41 { 42 m_data = bits.m_data; 43 m_owns = true; 44 m_bitsCapacity = bits.m_bitsCapacity; 45 m_bitsLength = bits.m_bitsLength; 46 uchar* t_data = new uchar[BitsToBytes(m_bitsCapacity)]; 47 memcpy(t_data,m_data,BitsToBytes(m_bitsCapacity)); 48 m_data = t_data; 49 return * this; 50 } 51 52 BitArray& BitArray:: operator =(BitArray&& bits) 53 { 54 m_data = bits.m_data; 55 m_owns = true; 56 m_bitsCapacity = bits.m_bitsCapacity; 57 m_bitsLength = bits.m_bitsLength; 58 bits.m_owns = false; 59 bits.m_data = nullptr; 60 return * this; 61 } 62 63 BitArray::BitArray(size_t bitsLength,size_t bitsCapacity) 64 { 65 /* * 66 整体思路：如果 bitsCapacity==0 ，那么默认容量将以 bitsLength乘以默认系数扩增 67 * */ 68 // 69 m_bitsLength = bitsLength; 70 m_owns = true; 71 size_t t_fact_bitsCapacity = bitsCapacity; 72 if( t_fact_bitsCapacity < bitsLength){ 73 t_fact_bitsCapacity = size_t(c_increaseCapacity*bitsLength); 74 } 75 size_t t_fact_bytesCapacity = BitsToBytes(t_fact_bitsCapacity); 76 m_bitsCapacity = 8*t_fact_bytesCapacity; 77 m_data = new uchar[t_fact_bytesCapacity]; 78 if(!m_data){ 79 // 内存分配失败逻辑 80 throw std::bad_alloc(); // ("can't allow memory!"); 81 } 82 memset(m_data, 0,t_fact_bytesCapacity); 83 } 84 85 BitArray::~BitArray() 86 { 87 if(m_owns && m_data != nullptr ) 88 delete[] m_data; 89 } 90 91 bool BitArray:: operator==(BitArray &bits) 92 { 93 if(m_bitsLength != bits.m_bitsLength) 94 return false; 95 for( int i= 0;i<m_bitsLength;i++){ 96 if( get(i) != bits. get(i) ){ 97 return false; 98 } 99 } 100 return true; 101 } 102 103 BitArray::BitArray(unsigned char* data, int bitsLength, bool isClear, bool isOwns) 104 { 105 m_data = data; 106 m_bitsLength = bitsLength; 107 m_bitsCapacity = 8*BitsToBytes(m_bitsLength); 108 m_owns = isOwns; 109 size_t t_bytesLength = BitsToBytes(m_bitsLength); 110 if(isClear) 111 memset(m_data, 0,t_bytesLength); 112 } 113 114 void BitArray::setData(unsigned char* data, int bitsLength, bool isClear, bool isOwns){ 115 if(m_owns && m_data != nullptr ) 116 delete[] m_data; 117 m_data = data; 118 m_bitsLength = bitsLength; 119 m_bitsCapacity = 8*BitsToBytes(m_bitsLength); 120 m_owns = isOwns; 121 size_t t_bytesLength = BitsToBytes(m_bitsLength); 122 if(isClear) 123 memset(m_data, 0,t_bytesLength); 124 } 125 126 bool BitArray:: set( int position, bool bit, bool isAllowOutOfRange, bool isAllowOutOfSize, bool isAllowToInfinite) 127 { 128 /* * 129 整体思路：将position分为六个区间，(-INF,-m_len),[-m_len,0), 130 [0,m_len),[m_len,m_cap),[m_cap,c_max*m_cap),[c_max*m_cap,INF) 131 一定越界的范围:(-INF,-m_len) 132 越界与否取决于isAllowToInfinite：[c_max*m_cap,INF) 133 越界与否取决于isAllowedOutOfRange:[m_cap,c_max*m_cap) 及 isAllowToInfinite 134 越界与否取决于isAllowOutOfSize:[m_len,m_cap) 及 isAllowToInfinite 135 合法访问范围：[-m_len,0),[0,m_len), 136 * */ 137 // position比 -(int)m_bitsLength 还小，或者需要扩张的倍数超出c_maxAllowedOutOfBound,此时一定越界 138 if( position<-( int)m_bitsLength || (position>=size_t(c_maxAllowedOutOfBound*m_bitsCapacity)&&!isAllowToInfinite) ){ 139 throw std::out_of_range( " Out of range , This position is too larger! "); 140 } 141 // 注意 isAllowToInfinite ， 如果这个值为 true，那么其他的条件开关将被忽略 142 // 如果不允许进行自动扩张，而访问位置超出 m_bitsCapacity 143 if(!isAllowOutOfRange&&position>=m_bitsCapacity&&!isAllowToInfinite){ 144 throw std::out_of_range( " Out of range , You are not allowed to automatically expanded memory! "); 145 } 146 if(!isAllowOutOfSize&&position>=m_bitsLength&&!isAllowToInfinite){ 147 throw std::out_of_range( " Out of range , You are not allowed to amplification size automatically! "); 148 } 149 // 以负数进行访问，修正position的实际位置,使得 [-m_len,0) -> [0,m_len) 150 if( position < 0){ 151 position += m_bitsLength; 152 } 153 if( position < m_bitsLength){ 154 // 访问位置没有超出目前的长度 155 return writeBit(m_data,position,bit); 156 } else if( position >= m_bitsLength && position < m_bitsCapacity){ 157 // 访问的位置已经超出了目前的长度，但是并没有超出实际的容量 158 m_bitsLength = position+ 1; 159 return writeBit(m_data,position,bit); 160 } else{ 161 size_t t_new_bitsLength = position+ 1; 162 size_t t_new_bytesCapacity = BitsToBytes(c_increaseCapacity*t_new_bitsLength); 163 size_t t_new_bitsCapacity = 8*t_new_bytesCapacity; 164 uchar* t_data = new uchar[t_new_bytesCapacity]; 165 if(!t_data){ 166 // 内存分配失败逻辑 167 throw std::bad_alloc(); // ("can't allow memory!"); 168 } 169 memset(t_data, 0,t_new_bytesCapacity); 170 memcpy(t_data,m_data,BitsToBytes(m_bitsCapacity)); 171 if( m_owns ){ 172 delete[] m_data; 173 } 174 m_data = t_data; 175 m_bitsCapacity = t_new_bitsCapacity; 176 m_bitsLength = t_new_bitsLength; 177 m_owns = true; 178 return writeBit(m_data,position,bit); 179 } 180 } 181 182 bool BitArray:: get( int position) 183 { 184 if(position >= m_bitsLength || position < -( int)m_bitsLength ){ 185 // 访问越界,抛出异常 186 throw std::out_of_range( " The location of the access is illegal! "); 187 } 188 if( position < 0 && position >= -( int)m_bitsLength ){ 189 // 以负数进行访问，修正position的实际位置 190 position += m_bitsLength; 191 } 192 return readBit(m_data,position); 193 } 194 195 size_t BitArray::setBitSize(size_t newBitsLength) 196 { 197 size_t origin_bitsLength = m_bitsLength; 198 if( newBitsLength <= m_bitsCapacity){ 199 m_bitsLength = newBitsLength; 200 } else{ 201 // 既然需要将大小扩充至newBitsLength，那么在newBitsLength-1 处赋false即可完成该功能 202 set(newBitsLength- 1, false, true, true, true); 203 } 204 return origin_bitsLength; 205 } 206 207 size_t BitArray::setBitCapacity(size_t newBitsCapacity) 208 { 209 /* * 210 整体思路：无论新的容量是多少，显然当与原来大小不一样时是需要进行扩容的 211 但是如果新容量比原来的长度还小，那么长度必须进行修改 212 * */ 213 // 原来的容量必定为8的倍数 214 size_t origin_bytesCapacity = BitsToBytes(m_bitsCapacity); 215 size_t new_bytesCapacity = BitsToBytes(newBitsCapacity); 216 if( origin_bytesCapacity != new_bytesCapacity){ 217 uchar* t_data = new uchar[new_bytesCapacity]; 218 if(!t_data){ 219 // 内存分配失败逻辑 220 throw std::bad_alloc(); // ("can't allow memory!"); 221 } 222 memset(t_data, 0,new_bytesCapacity); 223 if( origin_bytesCapacity < new_bytesCapacity){ 224 // 如果新容量比原来的容量大，那么全部复制 225 memcpy(t_data,m_data,origin_bytesCapacity); 226 } else{ 227 // 如果新容量比原来的容量小，那么仅复制一部分 228 memcpy(t_data,m_data,new_bytesCapacity); 229 } 230 if( m_owns ){ 231 delete[] m_data; 232 } 233 m_data = t_data; 234 m_bitsCapacity = BytesToBits(new_bytesCapacity); 235 if( m_bitsLength > m_bitsCapacity){ 236 m_bitsLength = m_bitsCapacity; 237 } 238 m_owns = true; 239 } 240 return BytesToBits(origin_bytesCapacity); 241 } 242 243 bool BitArray::setOwns( bool owns) 244 { 245 bool r = m_owns; 246 m_owns = owns; 247 return r; 248 } 249 250 /* 251 在map的position位置写入bit 252 */ 253 bool writeBit(unsigned char *map, int position, bool bit) 254 { 255 // sub表示在szMap中的下标，pos表示在该位置中相应的比特位 256 int sub = (position) / 8; 257 int pos = 7 - (position) % 8; 258 if( bit ){ 259 map[sub] |= 1<<pos; // 打开位开关 260 } else{ 261 map[sub] &= ~( 1<<pos); // 关闭位开关 262 } 263 return true; 264 } 265 266 /* 267 读取map的position位置的bit数据 268 */ 269 bool readBit(unsigned char *map, int position) 270 { 271 // sub 代表 szMap中对应的下标，范围是[0,bitmapLength) ；pos为相应的bit位置，范围是[0,8) 272 int sub = (position)/ 8; 273 int pos = 7 - (position)% 8; 274 return bool( (map[sub]>>pos)& 1 ); 275 } 276 277 Bit::Bit(BitArray *bits, int position){ 278 m_bits = bits; 279 m_position = position; 280 } 281 282 Bit& Bit:: operator =( bool bit){ 283 m_bits-> set(m_position,bit, true); 284 return * this; 285 } 286 287 Bit:: operator bool(){ 288 return m_bits-> get(m_position); 289 }
posted on 2014-04-16 15:59 阅读( ...) 评论( ...)