|
设计一个Bitset类，要求实现以下功能： Bitset bs(20); bs[12]=1;///第12位置1 bs[3]=0;///第3为置0 要求：充分使用内存，不得使用数组保存每位数值。（就是说不能用一个int保存一位）。 我只知道如果写成函数的形式是很简单的，但是使用下标，重载时函数返回什么呢？？ |
|
|
当然也不能使用char保存每位，
要能够用4字节保存32位的结果。 |
|
|
重载[]操作符
|
|
|
重载[]返回布尔值吧。 |
|
|
上面的不对，我再想想。
|
|
class BitSet
{
public:
BitSet(void);
BitSet(int nBits);
~BitSet(void);
void operator=(bool bIn);
BitSet& operator[](int nPos );
private:
int m_nData;
int m_nBitsNum;
int m_nPos;
};
...
BitSet::BitSet(void)
{
m_nBitsNum = 0;
m_nData =0;
}
BitSet::BitSet( int nBits )
{
m_nBitsNum = nBits;
m_nData = 0;
}
void BitSet::operator=( bool bIn )
{
if (bIn)
{
m_nData = m_nData |(1<<m_nPos);
}
else
{
m_nData = m_nData & (~(1<<m_nPos));
}
}
BitSet& BitSet::operator[]( int nPos )
{
if (m_nBitsNum<nPos)
{
m_nPos = 0;
return *this;
}
else
{
m_nPos = nPos;
return *this;
}
}
|
|
| 5分 |
STL库中有个bitset类，直接看看不就知道了！源码之前，了无秘密！
题目的意思就是让你用bit来表示bit，这是空间要求，但是要支持operator []的非const版本，因为C++不支持bit引用，如果直接做是行不通的，但是有个设计模式叫proxy，我们可以设计一个类让它代理对bit的访问，看起来又像引用，就可以达到题目的要求。 此题如果熟悉STL，木有难度。如果自己想，就需要有点模式的知识了。STL和模式对C++程序员来说应该是升级为基本技能。 供参考 |
class Bitset {
private:
int m_data;
int m_pos;
public:
Bitset(int val) { m_data = val; }
Bitset & operator[](int pos)
{
assert(pos < 32);
m_pos = pos;
return *this;
}
void operator=(bool bValue)
{
m_data |= bValue << m_pos;
}
friend ostream & operator<<(ostream & os, const Bitset & bit)
{
os << bit.m_data;
return os;
}
};
|
|
|
void operator=(bool bValue)实现有误，请无视 |
|
|
STL代码都公开的, 直接进去看看不就知道了?
内部用变量各个位实现的, 重载操作符很多, proxy模式.. |
|
|
显然你没弄懂我题目要求的意思。。。。 |
|
|
你说的很对。 “因为C++不支持bit引用，如果直接做是行不通的，但是有个设计模式叫proxy，我们可以设计一个类让它代理对bit的访问，看起来又像引用，就可以达到题目的要求。” |
|
| 35分 |
class my_bitset
{
public:
my_bitset(int bitsize) : bitsize(bitsize), length((bitsize + 7) >> 3), p(new unsigned char [length])
{
memset(p, 0, length);
}
void setbit(int index)
{
assert(0 <= index && index < bitsize);
p[index >> 3] |= (1 << (index & 7));
}
void clrbit(int index)
{
assert(0 <= index && index < bitsize);
p[index >> 3] &= ~(1 << (index & 7));
}
bool readbit(int index)const
{
assert(0 <= index && index < bitsize);
return (p[index >> 3] & (1 << (index & 7))) != 0;
}
~my_bitset()
{
delete[] p;
}
class proxy
{
public:
proxy(my_bitset &ref, size_t index) : ref(ref), index(index)
{
}
proxy &operator=(bool val)
{
if (val)
ref.setbit(index);
else
ref.clrbit(index);
return *this;
}
proxy &operator=(const proxy &rhs)
{
if (rhs.ref.readbit(rhs.index))
ref.setbit(index);
else
ref.clrbit(index);
return *this;
}
operator bool()
{
return ref.readbit(index);
}
private:
my_bitset &ref;
size_t index;
};
proxy operator[](int index)
{
return proxy(*this, index);
}
const proxy operator[](int index)const
{
return proxy(const_cast<my_bitset &>(*this), index);
}
private:
friend class proxy;
int bitsize;
int length;
unsigned char *p;
};
|
|
最近正打算看STL源码剖析，mark一下
|
|
|
非常感谢！ |
|
|
而且我们的id相似度这么高~ |
|
|
楼主看看这篇文章，大概能解决你的问题，希望我的回复不会太晚！呵呵
http://blog.csdn.net/focusing_on_cpp/article/details/45972981 |
|
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明如何实现bitset？–面试题！