贴一个BitSet类，请大家拍砖^_^

tyc611

需要一个类，能实现一些简单的位操作，标准库的bitset类提供了很好的功能，但它的大小由其模板参数决定。这使我们不能在运行时确定大小，于是自己动手写了个，实现了一些简单的操作（操作基本完备），请大家拍砖^_^

大家有什么好的建议或者想法，欢迎探讨。另外，这个类只简单地测试了下下，如果发现什么Bug或者不完备的地方，还望指出，谢谢

谢谢网友 awake 的建议！

1. 
   
2. // BitSet.h
   
3. 
   
4. #ifndef BITSET_H
   
5. #define BITSET_H
   
6. 
   
7. #include <iostream>
   
8. #include <stdexcept>
   
9. #include <limits>
   
10. 
    
11. // Class BitSet:
    
12. //   Class BitSet is a sequence of bits, and some operations are defined on it.
    
13. // Notes:
    
14. // (1) When an operation will be done on the bit at position 'pos',
    
15. //       you have to be sure that 'pos' satisfies the inequation pos < size(),
    
16. //       where size() returns the number of bits in this BitSet object.
    
17. //     If pos >= size(), an exception with type out_of_range will be thrown.
    
18. //     Note that the position 'pos' starts at zero.
    
19. // (2) In these operators: &=, |=, ^=, &, | and ^,
    
20. //       if the two BitSet objects have unequal values returned by size() ,
    
21. //       then an exception with type lenth_error will be thrown.
    
22. // (3) When the memory allocation fails, an exception with type bad_alloc will be thrown.
    
23. class BitSet
    
24. {
    
25. public:
    
26.     typedef unsigned long block_type;
    
27.     typedef unsigned long size_type;
    
28.    
    
29. private:
    
30.     enum {BLOCK_BYTES = sizeof(block_type)};
    
31.     enum {BLOCK_BITS = std::numeric_limits<block_type>::digits};
    
32.    
    
33. public:
    
34.     //--- copy control functions -------------------------
    
35.     BitSet(size_type bitNum);
    
36.     BitSet(const BitSet& bits);
    
37.     BitSet& operator= (const BitSet&);
    
38.     ~BitSet();
    
39.    
    
40.     //--- bit opearations --------------------------------
    
41.     // left-shift operator
    
42.     BitSet& operator<<= (size_type num);   
    
43.     // right-shift operator
    
44.     BitSet& operator>>= (size_type num);
    
45.    
    
46.     // set the bit at position pos when tagSet is true(default); otherwise, clear the bit
    
47.     BitSet& set(size_type pos, bool tagSet = true);
    
48.     // clear all the bits when tagClear is true(default); otherwise, set all the bits
    
49.     BitSet& clear(bool tagClear = true);
    
50.    
    
51.     // flip all the bits
    
52.     BitSet& flip();
    
53.     BitSet operator~ ();
    
54.     // flip the bit at position pos
    
55.     BitSet& flip(size_type pos);
    
56.    
    
57.     // test the bit at position pos
    
58.     bool test(size_type pos) const;   
    
59. 
    
60.     //--- operation between two BitSet objects-----------------
    
61.     BitSet& operator&= (const BitSet& bit);     // bitwise AND
    
62.     BitSet& operator|= (const BitSet& bit);     // bitwise inclusive OR
    
63.     BitSet& operator^= (const BitSet& bit);     // bitwise exclusive OR
    
64.     bool operator== (const BitSet&) const;      // equal: bitwise equal
    
65.    
    
66.     // get the number of bits in this BitSet object
    
67.     size_type size() const;
    
68.    
    
69. private:
    
70.     void leftShift(size_type num);    // left shift
    
71.     void rightShift(size_type num);   // right shift   
    
72. 
    
73. private:
    
74.     size_type m_bitNum;    // the number of bits in this BitSet object
    
75.     size_type m_size;      // the number of elements with type BitSet::block_type used to store the bits
    
76.     block_type *m_pBits;   // a pointer to an array with element type BitSet::block_type,
    
77.                            // used to store the bits information
    
78.     block_type m_mask;     // used to filter the redundant bits
    
79.                            // in the array element with the highest address
    
80. };
    
81. 
    
82. // declarations of nonmember functions
    
83. BitSet operator<< (const BitSet&, BitSet::size_type);   // left-shift operator
    
84. BitSet operator>> (const BitSet&, BitSet::size_type);   // right-shift operator
    
85. BitSet operator& (const BitSet&, const BitSet&);        // bitwise AND
    
86. BitSet operator| (const BitSet&, const BitSet&);        // bitwise inclusive OR
    
87. BitSet operator^ (const BitSet&, const BitSet&);        // bitwise exclusive OR
    
88. bool operator!= (const BitSet&, const BitSet&);         // not equal
    
89. 
    
90. //--- inline member functions ----------------------------------
    
91. //--- copy control functions --------------------
    
92. inline BitSet::BitSet(size_type bitNum)
    
93. {
    
94.     m_bitNum = bitNum;
    
95.     size_type freeBits = (BLOCK_BITS - m_bitNum % BLOCK_BITS) % BLOCK_BITS;
    
96.     m_size = m_bitNum / BLOCK_BITS + (freeBits == 0 ? 0 : 1);
    
97.     m_pBits = new block_type[m_size];
    
98.     if (m_pBits == NULL)
    
99.         throw std::bad_alloc();
    
100.     clear();  // clear all bits
     
101.     // calculate the mask value
     
102.     m_mask = ~block_type(0);
     
103.     m_mask >>= freeBits;
     
104. }
     
105. 
     
106. inline BitSet::BitSet(const BitSet& bit)
     
107. {
     
108.     m_size = bit.m_size;
     
109.     m_pBits = new block_type[m_size];
     
110.     if (m_pBits == NULL)
     
111.         throw std::bad_alloc();
     
112.     memcpy(m_pBits, bit.m_pBits, m_size * BLOCK_BYTES);
     
113.     m_bitNum = bit.m_bitNum;
     
114.     m_mask = bit.m_mask;
     
115. }
     
116. 
     
117. inline BitSet& BitSet::operator= (const BitSet& bit)
     
118. {
     
119.     if (this == &bit)    // self assignment
     
120.         return (*this);
     
121.     if (m_size != bit.m_size) {
     
122.         delete [] m_pBits;
     
123.         m_size = bit.m_size;
     
124.         m_pBits = new block_type[m_size];
     
125.         if (m_pBits == NULL)
     
126.             throw std::bad_alloc();
     
127.     }
     
128.     memcpy(m_pBits, bit.m_pBits, m_size * BLOCK_BYTES);
     
129.     m_bitNum = bit.m_bitNum;
     
130.     m_mask = bit.m_mask;
     
131.     return (*this);
     
132. }
     
133. 
     
134. inline BitSet::~BitSet()
     
135. {
     
136.     delete [] m_pBits;
     
137. }
     
138. 
     
139. //--- bit opearations -----------------------------
     
140. // left shift operator
     
141. inline BitSet& BitSet::operator<<= (size_type num)
     
142. {
     
143.     leftShift(num);
     
144.     return (*this);
     
145. }
     
146. 
     
147. // right shift operator
     
148. inline BitSet& BitSet::operator>>= (size_type num)
     
149. {
     
150.     rightShift(num);
     
151.     return (*this);
     
152. }
     
153. 
     
154. // clear all the bits when tagClear is true(default); otherwise, set all the bits
     
155. inline BitSet& BitSet::clear(bool tagClear)
     
156. {
     
157.     if (tagClear)
     
158.         memset(m_pBits, 0, m_size * BLOCK_BYTES);
     
159.     else {
     
160.         memset(m_pBits, (int)std::numeric_limits<unsigned char>::max(), m_size * BLOCK_BYTES);
     
161.         m_pBits[m_size-1] &= m_mask;  // filter the redundant bits
     
162.     }
     
163.     return (*this);
     
164. }
     
165. 
     
166. // flip all the bits
     
167. inline BitSet& BitSet::flip()
     
168. {
     
169.     for (size_type i = 0; i < m_size; ++i)
     
170.         m_pBits[i] = ~m_pBits[i];
     
171.     m_pBits[m_size-1] &= m_mask;  // filter the redundant bits
     
172.     return (*this);
     
173. }
     
174. 
     
175. // flip all the bits
     
176. inline BitSet BitSet::operator~ ()
     
177. {
     
178.     return BitSet(*this).flip();
     
179. }  
     
180. 
     
181. //--- operation between two BitSet objects-----------------
     
182. // bitwise AND
     
183. inline BitSet& BitSet::operator&= (const BitSet& bit)
     
184. {
     
185.     if (m_bitNum != bit.m_bitNum)
     
186.         throw std::length_error("Error: two BitSet objects have not equal lengths");
     
187.     for (size_type i = 0; i < m_size; ++i)
     
188.         m_pBits[i] &= bit.m_pBits[i];
     
189.     return (*this);
     
190. }
     
191. 
     
192. // bitwise inclusive OR
     
193. inline BitSet& BitSet::operator|= (const BitSet& bit)
     
194. {
     
195.     if (m_bitNum != bit.m_bitNum)
     
196.         throw std::length_error("Error: two BitSet objects have not equal lengths");
     
197.     for (size_type i = 0; i < m_size; ++i)
     
198.         m_pBits[i] |= bit.m_pBits[i];
     
199.     return (*this);
     
200. }
     
201. 
     
202. // bitwise exclusive OR
     
203. inline BitSet& BitSet::operator^= (const BitSet& bit)
     
204. {
     
205.     if (m_bitNum != bit.m_bitNum)
     
206.         throw std::length_error("Error: two BitSet objects have not equal lengths");
     
207.     for (size_type i = 0; i < m_size; ++i)
     
208.         m_pBits[i] ^= bit.m_pBits[i];
     
209.     return (*this);
     
210. }
     
211. 
     
212. // equal: bitwise equal
     
213. inline bool BitSet::operator== (const BitSet &bit) const
     
214. {
     
215.     if (m_bitNum != bit.m_bitNum)
     
216.         return false;
     
217.     for (size_type i = 0; i < m_size; ++i)
     
218.         if (m_pBits[i] != bit.m_pBits[i])
     
219.             return false;
     
220.     return true;
     
221. }
     
222. 
     
223. // get the number of bits in this BitSet object
     
224. inline BitSet::size_type BitSet::size() const
     
225. {
     
226.     return m_bitNum;
     
227. }
     
228. 
     
229. //--- nonmember functions -----------------------------------
     
230. // left shift operator
     
231. inline BitSet operator<< (const BitSet &bit, BitSet::size_type num)
     
232. {
     
233.     return BitSet(bit) <<= num;
     
234. }
     
235. 
     
236. // right shift operator
     
237. inline BitSet operator>> (const BitSet &bit, BitSet::size_type num)
     
238. {
     
239.     return BitSet(bit) >>= num;
     
240. }
     
241. 
     
242. // bitwise AND
     
243. inline BitSet operator& (const BitSet &lhs, const BitSet &rhs)
     
244. {
     
245.     return BitSet(lhs) &= rhs;
     
246. }
     
247. 
     
248. // bitwise inclusive OR
     
249. inline BitSet operator| (const BitSet &lhs, const BitSet &rhs)
     
250. {
     
251.     return BitSet(lhs) |= rhs;
     
252. }
     
253. 
     
254. // bitwise exclusive OR
     
255. inline BitSet operator^ (const BitSet &lhs, const BitSet &rhs)
     
256. {
     
257.     return BitSet(lhs) ^= rhs;
     
258. }
     
259. 
     
260. // not equal
     
261. inline bool operator!= (const BitSet &lhs, const BitSet &rhs)
     
262. {
     
263.     return !(lhs == rhs);
     
264. }
     
265. 
     
266. // endif: BITSET_H
     
267. #endif
     

复制代码

1. 
   
2. // BitSet.cpp
   
3. 
   
4. #include <iostream>
   
5. #include <iomanip>
   
6. #include <stdexcept>
   
7. #include "BitSet.h"
   
8. 
   
9. //--- bit operation ----------------------------------------
   
10. void BitSet::leftShift(size_type num)
    
11. {
    
12.     // function: left-shift num bits
    
13.     if (num >= m_bitNum) {
    
14.         // when the number of bits asked to shift is more than
    
15.         // that possessed by the object, just clear all the bits.
    
16.         clear();
    
17.         return ;
    
18.     }
    
19. 
    
20.     // compute the corresponding number of
    
21.     // elements(ULONG) and the remaining bits
    
22.     size_type eleNum = num / BLOCK_BITS;
    
23.     size_type bitNum = num % BLOCK_BITS;
    
24.    
    
25.     // first left-shift eleNum elements
    
26.     if (eleNum != 0) {
    
27.         block_type* pTmp = new block_type[m_size];
    
28.         if (pTmp == NULL)
    
29.             throw std::bad_alloc();
    
30.         memcpy(pTmp, m_pBits, (m_size - eleNum) * BLOCK_BYTES);
    
31.         memcpy(m_pBits + eleNum, pTmp, (m_size - eleNum) * BLOCK_BYTES);
    
32.         memset(m_pBits, 0, eleNum * BLOCK_BYTES);
    
33.         delete [] pTmp;
    
34.     }
    
35. 
    
36.     // next, left-shift bitNum bits (1 <= bitNum <= ULONG_BITS - 1)
    
37.     if (bitNum != 0) {
    
38.         block_type *pTmp  = m_pBits + m_size - 1;
    
39.         for ( ; pTmp > m_pBits; --pTmp) {
    
40.             *pTmp = (*pTmp << bitNum) | (*(pTmp - 1) >> (BLOCK_BITS - bitNum));
    
41.         }
    
42.         *pTmp <<= bitNum;
    
43.     }
    
44.     m_pBits[m_size-1] &= m_mask;      // filter the redundant bits
    
45. }
    
46. 
    
47. void BitSet::rightShift(size_type num)
    
48. {
    
49.     // function: right-shift num bits
    
50.     if (num >= m_bitNum) {
    
51.         // when the number of bits asked to shift is more than
    
52.         // that possessed by the object, just clear all the bits.
    
53.         clear();
    
54.         return ;
    
55.     }
    
56. 
    
57.     // compute the corresponding number of elements(ULONG) and remaining bits
    
58.     size_type eleNum = num / BLOCK_BITS;
    
59.     size_type bitNum = num % BLOCK_BITS;
    
60.    
    
61.     // first right-shift eleNum elements
    
62.     if (eleNum != 0) {
    
63.         block_type* pTmp = new block_type[m_size];
    
64.         if (pTmp == NULL)
    
65.             throw std::bad_alloc();
    
66.         memcpy(pTmp, m_pBits + eleNum, (m_size - eleNum) * BLOCK_BYTES);
    
67.         memcpy(m_pBits, pTmp, (m_size - eleNum) * BLOCK_BYTES);
    
68.         memset(m_pBits + m_size - eleNum, 0, eleNum * BLOCK_BYTES);
    
69.         delete [] pTmp;
    
70.     }
    
71. 
    
72.     // next, right-shift bitNum bits (1 <= bitNum <= ULONG_BITS - 1)
    
73.     if (bitNum != 0) {
    
74.         block_type *pTmp  = m_pBits;
    
75.         for ( ; pTmp < m_pBits + m_size - 1; ++pTmp) {
    
76.             *pTmp = (*pTmp >> bitNum) | (*(pTmp + 1) << (BLOCK_BITS - bitNum));
    
77.         }
    
78.         *pTmp >>= bitNum;
    
79.     }
    
80. }
    
81. 
    
82. BitSet& BitSet::set(size_type pos, bool tagSet)
    
83. {
    
84.     // function: set the bit at position pos (beginning from 0) when tagSet is true;
    
85.     //           otherwise, clear the bit.
    
86.     if (pos >= m_bitNum)
    
87.         throw std::out_of_range("Error: out of range in fuction set");
    
88.    
    
89.     // compute the corresponding index of elements(ULONG) and remaining bits
    
90.     size_type eleIndex = pos / BLOCK_BITS;
    
91.     size_type bitIndex = pos % BLOCK_BITS;
    
92.    
    
93.     block_type mask = 1;
    
94.     mask <<= bitIndex;
    
95.     if (!tagSet)
    
96.         mask = ~mask;
    
97.     m_pBits[eleIndex] = tagSet ? (m_pBits[eleIndex] | mask) : (m_pBits[eleIndex] & mask);
    
98.     return (*this);
    
99. }
    
100. 
     
101. BitSet& BitSet::flip(size_type pos)
     
102. {
     
103.     // function: flip the bit at position pos
     
104.     if (pos >= m_bitNum)
     
105.         throw std::out_of_range("Error: out of range in fuction set");
     
106.    
     
107.     // compute the corresponding index of elements(ULONG) and remaining bits
     
108.     size_type eleIndex = pos / BLOCK_BITS;
     
109.     size_type bitIndex = pos % BLOCK_BITS;
     
110.    
     
111.     block_type mask = 1;
     
112.     mask <<= bitIndex;
     
113.     m_pBits[eleIndex] = (m_pBits[eleIndex] & mask) ? (m_pBits[eleIndex] & ~mask) : (m_pBits[eleIndex] | mask);
     
114.     return (*this);
     
115. }
     
116. 
     
117. bool BitSet::test(size_type pos) const
     
118. {
     
119.     // function: test the bit at position pos.
     
120.     // return:   If the bit is set, then return true; otherwise return false.
     
121.     if (pos >= m_bitNum)
     
122.         throw std::out_of_range("Error: out of range in fuction set");
     
123.    
     
124.     // compute the corresponding index of elements(ULONG) and remaining bits
     
125.     size_type eleIndex = pos / BLOCK_BITS;
     
126.     size_type bitIndex = pos % BLOCK_BITS;
     
127.    
     
128.     block_type mask = 1;
     
129.     mask <<= bitIndex;
     
130.     return m_pBits[eleIndex] & mask;
     
131. }
     

复制代码

[ 本帖最后由 tyc611 于 2007-4-21 14:20 编辑 ]

tyc611

贴一个用该类实现的算法：实现子集和数问题的判定性问题^_^

1. 
   
2. #include <iostream>
   
3. #include "BitSet.h"
   
4. 
   
5. bool SubsetSum(ULONG *nums, int num, ULONG sum);
   
6. 
   
7. int main()
   
8. {
   
9.     ULONG nums[6] = {5, 10, 12, 13, 15, 18};
   
10.     std::cout << std::boolalpha << SubsetSum(nums, 6, 30) << std::endl;
    
11.    
    
12.     return 0;
    
13. }
    
14. 
    
15. bool SubsetSum(ULONG *nums, int num, ULONG sum)
    
16. {
    
17.     BitSet bit(sum + 1);
    
18.     bit.set(0);
    
19.     for (int i = 0; i < num; ++i) {
    
20.         bit |= (bit << nums[i]);
    
21.         if (bit.test(sum))
    
22.             return true;
    
23.     }
    
24.     return false;
    
25. }
    

复制代码

langue

不错。我就不多加评论了。

tyc611

原帖由 langue 于 2007-4-14 19:57 发表
不错。我就不多加评论了。

谢谢版主^_^

希望大家多多讨论^_^

mik

顶~

writer15

hehe, 楼主在哪个项目用了bitset了？p2p2? bittorrent?

emacsnw

不错不错，支持一把。

doctorjxd

支持楼主！


不过相同功能的Bitset类已经由Boost写出来了。
使用方法见：
http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html

tyc611

原帖由 doctorjxd 于 2007-4-20 21:08 发表
支持楼主！


不过相同功能的Bitset类已经由Boost写出来了。
使用方法见：
http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html

不知道有这东西呢，又做了无用功，权当练手
已经下了库回来，研究下它怎么移位的

awake

我来提几个建议吧，大家一起讨论：
考虑使用unsigned char代替unsigned long。
去掉所有的inline关键字。
把所有的typedef和常数放在class之内。
不要检查内存分配失败。
friend函数不必成为friend。
operator<<()是否应该为const？
考虑使用numeric_limits<unsigned long>::digits。
考虑提供命名操作，如and。
考虑提供swap操作。