如何实现bitset?–面试题

C++语言 码拜 10年前 (2015-05-11) 1206次浏览 0个评论
 

设计一个Bitset类,要求实现以下功能:

Bitset bs(20);
bs[12]=1;///第12位置1
bs[3]=0;///第3为置0

要求:充分使用内存,不得使用数组保存每位数值。(就是说不能用一个int保存一位)。

我只知道如果写成函数的形式是很简单的,但是使用下标,重载时函数返回什么呢??

当然也不能使用char保存每位,
要能够用4字节保存32位的结果。
重载[]操作符
引用 楼主 hello_world_2012 的回复:

设计一个Bitset类,要求实现以下功能:

Bitset bs(20);
bs[12]=1;///第12位置1
bs[3]=0;///第3为置0

要求:充分使用内存,不得使用数组保存每位数值。(就是说不能用一个int保存一位)。

我只知道如果写成函数的形式是很简单的,但是使用下标,重载时函数返回什么呢??

重载[]返回布尔值吧。
bool operator[](int x);

上面的不对,我再想想。
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;
    }
};
引用 7 楼 wuxupu 的回复:
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模式..
引用 5 楼 cmail2005 的回复:
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;
	}
}

显然你没弄懂我题目要求的意思。。。。
只用一个int保存只能小于32位,多余32位保存不了;
而且你的operator=、operator[]也有问题。

引用 6 楼 lxhscx 的回复:

STL库中有个bitset类,直接看看不就知道了!源码之前,了无秘密!

题目的意思就是让你用bit来表示bit,这是空间要求,但是要支持operator []的非const版本,因为C++不支持bit引用,如果直接做是行不通的,但是有个设计模式叫proxy,我们可以设计一个类让它代理对bit的访问,看起来又像引用,就可以达到题目的要求。

此题如果熟悉STL,木有难度。如果自己想,就需要有点模式的知识了。STL和模式对C++程序员来说应该是升级为基本技能。

供参考

你说的很对。
但是stl中这个写的太复杂,我也不太熟悉stl源码。。。我想知道怎么用简洁的代码实现这个需求,

“因为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一下
引用 12 楼 hello_world000 的回复:
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;
};

非常感谢!

引用 12 楼 hello_world000 的回复:
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;
};

而且我们的id相似度这么高~

楼主看看这篇文章,大概能解决你的问题,希望我的回复不会太晚!呵呵
http://blog.csdn.net/focusing_on_cpp/article/details/45972981

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明如何实现bitset?–面试题
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!