需要一个类，能实现一些简单的位操作，标准库的bitset类提供了很好的功能，但它的大小由其模板参数决定。这使我们不能在运行时确定大小，于是自己动手写了个，实现了一些简单的操作（操作基本完备），请大家拍砖^_^
大家有什么好的建议或者想法，欢迎探讨。另外，这个类只简单地测试了下下，如果发现什么Bug或者不完备的地方，还望指出，谢谢
[color=Blue]谢谢网友 awake 的建议！[/color]
// BitSet.h
#ifndef BITSET_H
#define BITSET_H
#include <iostream>
#include <stdexcept>
#include <limits>
// Class BitSet:
// Class BitSet is a sequence of bits, and some operations are defined on it.
// Notes:
// (1) When an operation will be done on the bit at position 'pos',
// you have to be sure that 'pos' satisfies the inequation pos < size(),
// where size() returns the number of bits in this BitSet object.
// If pos >= size(), an exception with type out_of_range will be thrown.
// Note that the position 'pos' starts at zero.
// (2) In these operators: &=, |=, ^=, &, | and ^,
// if the two BitSet objects have unequal values returned by size() ,
// then an exception with type lenth_error will be thrown.
// (3) When the memory allocation fails, an exception with type bad_alloc will be thrown.
class BitSet
{
public:
typedef unsigned long block_type;
typedef unsigned long size_type;
private:
enum {BLOCK_BYTES = sizeof(block_type)};
enum {BLOCK_BITS = std::numeric_limits<block_type>::digits};
public:
//--- copy control functions -------------------------
BitSet(size_type bitNum);
BitSet(const BitSet& bits);
BitSet& operator= (const BitSet&);
~BitSet();
//--- bit opearations --------------------------------
// left-shift operator
BitSet& operator<<= (size_type num);
// right-shift operator
BitSet& operator>>= (size_type num);
// set the bit at position pos when tagSet is true(default); otherwise, clear the bit
BitSet& set(size_type pos, bool tagSet = true);
// clear all the bits when tagClear is true(default); otherwise, set all the bits
BitSet& clear(bool tagClear = true);
// flip all the bits
BitSet& flip();
BitSet operator~ ();
// flip the bit at position pos
BitSet& flip(size_type pos);
// test the bit at position pos
bool test(size_type pos) const;
//--- operation between two BitSet objects-----------------
BitSet& operator&= (const BitSet& bit); // bitwise AND
BitSet& operator|= (const BitSet& bit); // bitwise inclusive OR
BitSet& operator^= (const BitSet& bit); // bitwise exclusive OR
bool operator== (const BitSet&) const; // equal: bitwise equal
// get the number of bits in this BitSet object
size_type size() const;
private:
void leftShift(size_type num); // left shift
void rightShift(size_type num); // right shift
private:
size_type m_bitNum; // the number of bits in this BitSet object
size_type m_size; // the number of elements with type BitSet::block_type used to store the bits
block_type *m_pBits; // a pointer to an array with element type BitSet::block_type,
// used to store the bits information
block_type m_mask; // used to filter the redundant bits
// in the array element with the highest address
};
// declarations of nonmember functions
BitSet operator<< (const BitSet&, BitSet::size_type); // left-shift operator
BitSet operator>> (const BitSet&, BitSet::size_type); // right-shift operator
BitSet operator& (const BitSet&, const BitSet&); // bitwise AND
BitSet operator| (const BitSet&, const BitSet&); // bitwise inclusive OR
BitSet operator^ (const BitSet&, const BitSet&); // bitwise exclusive OR
bool operator!= (const BitSet&, const BitSet&); // not equal
//--- inline member functions ----------------------------------
//--- copy control functions --------------------
inline BitSet::BitSet(size_type bitNum)
{
m_bitNum = bitNum;
size_type freeBits = (BLOCK_BITS - m_bitNum % BLOCK_BITS) % BLOCK_BITS;
m_size = m_bitNum / BLOCK_BITS + (freeBits == 0 ? 0 : 1);
m_pBits = new block_type[m_size];
if (m_pBits == NULL)
throw std::bad_alloc();
clear(); // clear all bits
// calculate the mask value
m_mask = ~block_type(0);
m_mask >>= freeBits;
}
inline BitSet::BitSet(const BitSet& bit)
{
m_size = bit.m_size;
m_pBits = new block_type[m_size];
if (m_pBits == NULL)
throw std::bad_alloc();
memcpy(m_pBits, bit.m_pBits, m_size * BLOCK_BYTES);
m_bitNum = bit.m_bitNum;
m_mask = bit.m_mask;
}
inline BitSet& BitSet::operator= (const BitSet& bit)
{
if (this == &bit) // self assignment
return (*this);
if (m_size != bit.m_size) {
delete [] m_pBits;
m_size = bit.m_size;
m_pBits = new block_type[m_size];
if (m_pBits == NULL)
throw std::bad_alloc();
}
memcpy(m_pBits, bit.m_pBits, m_size * BLOCK_BYTES);
m_bitNum = bit.m_bitNum;
m_mask = bit.m_mask;
return (*this);
}
inline BitSet::~BitSet()
{
delete [] m_pBits;
}
//--- bit opearations -----------------------------
// left shift operator
inline BitSet& BitSet::operator<<= (size_type num)
{
leftShift(num);
return (*this);
}
// right shift operator
inline BitSet& BitSet::operator>>= (size_type num)
{
rightShift(num);
return (*this);
}
// clear all the bits when tagClear is true(default); otherwise, set all the bits
inline BitSet& BitSet::clear(bool tagClear)
{
if (tagClear)
memset(m_pBits, 0, m_size * BLOCK_BYTES);
else {
memset(m_pBits, (int)std::numeric_limits<unsigned char>::max(), m_size * BLOCK_BYTES);
m_pBits[m_size-1] &= m_mask; // filter the redundant bits
}
return (*this);
}
// flip all the bits
inline BitSet& BitSet::flip()
{
for (size_type i = 0; i < m_size; ++i)
m_pBits = ~m_pBits;
m_pBits[m_size-1] &= m_mask; // filter the redundant bits
return (*this);
}
// flip all the bits
inline BitSet BitSet::operator~ ()
{
return BitSet(*this).flip();
}
//--- operation between two BitSet objects-----------------
// bitwise AND
inline BitSet& BitSet::operator&= (const BitSet& bit)
{
if (m_bitNum != bit.m_bitNum)
throw std::length_error("Error: two BitSet objects have not equal lengths");
for (size_type i = 0; i < m_size; ++i)
m_pBits &= bit.m_pBits;
return (*this);
}
// bitwise inclusive OR
inline BitSet& BitSet::operator|= (const BitSet& bit)
{
if (m_bitNum != bit.m_bitNum)
throw std::length_error("Error: two BitSet objects have not equal lengths");
for (size_type i = 0; i < m_size; ++i)
m_pBits |= bit.m_pBits;
return (*this);
}
// bitwise exclusive OR
inline BitSet& BitSet::operator^= (const BitSet& bit)
{
if (m_bitNum != bit.m_bitNum)
throw std::length_error("Error: two BitSet objects have not equal lengths");
for (size_type i = 0; i < m_size; ++i)
m_pBits ^= bit.m_pBits;
return (*this);
}
// equal: bitwise equal
inline bool BitSet::operator== (const BitSet &bit) const
{
if (m_bitNum != bit.m_bitNum)
return false;
for (size_type i = 0; i < m_size; ++i)
if (m_pBits != bit.m_pBits)
return false;
return true;
}
// get the number of bits in this BitSet object
inline BitSet::size_type BitSet::size() const
{
return m_bitNum;
}
//--- nonmember functions -----------------------------------
// left shift operator
inline BitSet operator<< (const BitSet &bit, BitSet::size_type num)
{
return BitSet(bit) <<= num;
}
// right shift operator
inline BitSet operator>> (const BitSet &bit, BitSet::size_type num)
{
return BitSet(bit) >>= num;
}
// bitwise AND
inline BitSet operator& (const BitSet &lhs, const BitSet &rhs)
{
return BitSet(lhs) &= rhs;
}
// bitwise inclusive OR
inline BitSet operator| (const BitSet &lhs, const BitSet &rhs)
{
return BitSet(lhs) |= rhs;
}
// bitwise exclusive OR
inline BitSet operator^ (const BitSet &lhs, const BitSet &rhs)
{
return BitSet(lhs) ^= rhs;
}
// not equal
inline bool operator!= (const BitSet &lhs, const BitSet &rhs)
{
return !(lhs == rhs);
}
// endif: BITSET_H
#endif
// BitSet.cpp
#include <iostream>
#include <iomanip>
#include <stdexcept>
#include "BitSet.h"
//--- bit operation ----------------------------------------
void BitSet::leftShift(size_type num)
{
// function: left-shift num bits
if (num >= m_bitNum) {
// when the number of bits asked to shift is more than
// that possessed by the object, just clear all the bits.
clear();
return ;
}
// compute the corresponding number of
// elements(ULONG) and the remaining bits
size_type eleNum = num / BLOCK_BITS;
size_type bitNum = num % BLOCK_BITS;
// first left-shift eleNum elements
if (eleNum != 0) {
block_type* pTmp = new block_type[m_size];
if (pTmp == NULL)
throw std::bad_alloc();
memcpy(pTmp, m_pBits, (m_size - eleNum) * BLOCK_BYTES);
memcpy(m_pBits + eleNum, pTmp, (m_size - eleNum) * BLOCK_BYTES);
memset(m_pBits, 0, eleNum * BLOCK_BYTES);
delete [] pTmp;
}
// next, left-shift bitNum bits (1 <= bitNum <= ULONG_BITS - 1)
if (bitNum != 0) {
block_type *pTmp = m_pBits + m_size - 1;
for ( ; pTmp > m_pBits; --pTmp) {
*pTmp = (*pTmp << bitNum) | (*(pTmp - 1) >> (BLOCK_BITS - bitNum));
}
*pTmp <<= bitNum;
}
m_pBits[m_size-1] &= m_mask; // filter the redundant bits
}
void BitSet::rightShift(size_type num)
{
// function: right-shift num bits
if (num >= m_bitNum) {
// when the number of bits asked to shift is more than
// that possessed by the object, just clear all the bits.
clear();
return ;
}
// compute the corresponding number of elements(ULONG) and remaining bits
size_type eleNum = num / BLOCK_BITS;
size_type bitNum = num % BLOCK_BITS;
// first right-shift eleNum elements
if (eleNum != 0) {
block_type* pTmp = new block_type[m_size];
if (pTmp == NULL)
throw std::bad_alloc();
memcpy(pTmp, m_pBits + eleNum, (m_size - eleNum) * BLOCK_BYTES);
memcpy(m_pBits, pTmp, (m_size - eleNum) * BLOCK_BYTES);
memset(m_pBits + m_size - eleNum, 0, eleNum * BLOCK_BYTES);
delete [] pTmp;
}
// next, right-shift bitNum bits (1 <= bitNum <= ULONG_BITS - 1)
if (bitNum != 0) {
block_type *pTmp = m_pBits;
for ( ; pTmp < m_pBits + m_size - 1; ++pTmp) {
*pTmp = (*pTmp >> bitNum) | (*(pTmp + 1) << (BLOCK_BITS - bitNum));
}
*pTmp >>= bitNum;
}
}
BitSet& BitSet::set(size_type pos, bool tagSet)
{
// function: set the bit at position pos (beginning from 0) when tagSet is true;
// otherwise, clear the bit.
if (pos >= m_bitNum)
throw std::out_of_range("Error: out of range in fuction set");
// compute the corresponding index of elements(ULONG) and remaining bits
size_type eleIndex = pos / BLOCK_BITS;
size_type bitIndex = pos % BLOCK_BITS;
block_type mask = 1;
mask <<= bitIndex;
if (!tagSet)
mask = ~mask;
m_pBits[eleIndex] = tagSet ? (m_pBits[eleIndex] | mask) : (m_pBits[eleIndex] & mask);
return (*this);
}
BitSet& BitSet::flip(size_type pos)
{
// function: flip the bit at position pos
if (pos >= m_bitNum)
throw std::out_of_range("Error: out of range in fuction set");
// compute the corresponding index of elements(ULONG) and remaining bits
size_type eleIndex = pos / BLOCK_BITS;
size_type bitIndex = pos % BLOCK_BITS;
block_type mask = 1;
mask <<= bitIndex;
m_pBits[eleIndex] = (m_pBits[eleIndex] & mask) ? (m_pBits[eleIndex] & ~mask) : (m_pBits[eleIndex] | mask);
return (*this);
}
bool BitSet::test(size_type pos) const
{
// function: test the bit at position pos.
// return: If the bit is set, then return true; otherwise return false.
if (pos >= m_bitNum)
throw std::out_of_range("Error: out of range in fuction set");
// compute the corresponding index of elements(ULONG) and remaining bits
size_type eleIndex = pos / BLOCK_BITS;
size_type bitIndex = pos % BLOCK_BITS;
block_type mask = 1;
mask <<= bitIndex;
return m_pBits[eleIndex] & mask;
}
[ 本帖最后由 tyc611 于 2007-4-21 14:20 编辑 ]
tyc611 回复于：2007-04-14 19:55:49
贴一个用该类实现的算法：实现子集和数问题的判定性问题^_^
#include <iostream>
#include "BitSet.h"
bool SubsetSum(ULONG *nums, int num, ULONG sum);
int main()
{
ULONG nums[6] = {5, 10, 12, 13, 15, 18};
std::cout << std::boolalpha << SubsetSum(nums, 6, 30) << std::endl;
return 0;
}
bool SubsetSum(ULONG *nums, int num, ULONG sum)
{
BitSet bit(sum + 1);
bit.set(0);
for (int i = 0; i < num; ++i) {
bit |= (bit << nums);
if (bit.test(sum))
return true;
}
return false;
}
langue 回复于：2007-04-14 19:57:39
不错。我就不多加评论了。
tyc611 回复于：2007-04-14 19:59:25
引用：原帖由 langue 于 2007-4-14 19:57 发表
不错。我就不多加评论了。
谢谢版主^_^
希望大家多多讨论^_^
mik 回复于：2007-04-14 20:27:06
顶~
writer15 回复于：2007-04-15 12:37:35
hehe, 楼主在哪个项目用了bitset了？p2p2? bittorrent?
emacsnw 回复于：2007-04-15 14:40:20
不错不错，支持一把。
doctorjxd 回复于：2007-04-20 21:08:10
支持楼主！
不过相同功能的Bitset类已经由Boost写出来了。
使用方法见：
http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html
tyc611 回复于：2007-04-20 22:28:44
引用：原帖由 doctorjxd 于 2007-4-20 21:08 发表
支持楼主！
不过相同功能的Bitset类已经由Boost写出来了。
使用方法见：
http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html
不知道有这东西呢，又做了无用功，权当练手:em15:
已经下了库回来，研究下它怎么移位的
awake 回复于：2007-04-21 01:12:34
我来提几个建议吧，大家一起讨论：
考虑使用unsigned char代替unsigned long。
去掉所有的inline关键字。
把所有的typedef和常数放在class之内。
不要检查内存分配失败。
friend函数不必成为friend。
operator<<()是否应该为const？
考虑使用numeric_limits<unsigned long>::digits。
考虑提供命名操作，如and。
考虑提供swap操作。
tyc611 回复于：2007-04-21 01:49:31
首先感谢你提出的建议，下面是我的一些看法
>> 考虑使用unsigned char代替unsigned long
请说明理由，谢谢。我之所以用unsigned long主要是从移位的效率来考虑的，因为当初的应用中存在大量移位运算
>> 去掉所有的inline关键字
大多数函数比较小，内联比较合适，可能个别需要商榷
>> 把所有的typedef和常数放在class之内
常数只用于类实现，应该放在类内部；但ULONG是提供给用户的接口中的类型，放在头文件中比较合适吧？
>> 不要检查内存分配失败
why?
>> friend函数不必成为friend
其实除了必须实现为friend的接口外，对于其它接口，是实现为friend还是成员函数，我一直不知道以何为标准，请指教
>> operator<<()是否应该为const？
恩，你是对的
>> 考虑使用numeric_limits<unsigned long>::digits。
这个用不着这么麻烦吧？
>> 考虑提供命名操作，如and。
>> 考虑提供swap操作
从执行效率来讲，应该实现swap操作，不然用等价操作代价太大。
其它这类操作还很多，这里并没有完全实现，如果需要可以自己做照写就行了。
awake 回复于：2007-04-21 12:30:05
呵呵，我也只是按我的经验说的一点想法。
效率的问题，这里我不是很清楚，我建议你测试一下，改起来应该很方便吧。我人比较倾向于使用unsigned char而已。
inline关键字只是一个建议，有些编译器直接忽略了这个关键字。而且究竟什么时候inline，编译器会更清楚。
typedef放在类中也是可以提供给用户的。比如Container::value_type。
不要检查内存分配失败，这一点可以参考《Exceptional C++ Style》。1、似乎从标准上来将，当内存分配失败的时候是不应该返回空指针的。2、很多平台上从来不会出现内存分配失败的情况。3、真正没有内存的时候，你恐怕没有空间抛出异常了。4、其他。
那些friend函数好像没有访问私有成员，为什么要加为friend呢？
据说有些机器上不是每个字节都8位，这应该可以成为使用umeric_limits<unsigned long>::digits的理由了。
tyc611 回复于：2007-04-21 12:59:21
>> 那些friend函数好像没有访问私有成员，为什么要加为friend呢？
对，我疏忽了:em15:
>> 据说有些机器上不是每个字节都8位，这应该可以成为使用umeric_limits<unsigned long>::digits的理由了。
接受建议，呵呵，不过我还真没见过这种机子
其它我再考虑下下，再次感谢
|
