在Linux C中寻找位图实现API

Question

我需要一个Linux C中的位图API。

我需要2^18个位，因此需要32KB的内存。并且我会经常在位图中设置和取消位。

所以基本上我需要以下API：

set_bitmap(int i)  // it sets the i-th bit to 1 in the bitmap
unset_bitmap(int i) // it sets the i-th bit to 0 in the bitmap
bitmap_t create_bitmap(int n) // it creates a bitmap of size n, like n=2^18

有没有任何源代码或类似的源代码？

谢谢！

- misteryes

---

可能是如何在C中实现位集？的重复问题。 - user405725

这是“code”，而不是“codes”！ - user405725

Answer 1

这并不难。

typedef unsigned char* bitmap_t;

void set_bitmap(bitmap_t b, int i) {
    b[i / 8] |= 1 << (i & 7);
}

void unset_bitmap(bitmap_t b, int i) {
    b[i / 8] &= ~(1 << (i & 7));
}

void get_bitmap(bitmap_t b, int i) {
    return b[i / 8] & (1 << (i & 7)) ? 1 : 0;
}

bitmap_t create_bitmap(int n) {
    return malloc((n + 7) / 8);
}

- Paul Hankin

Answer 2

在函数get_bitmap中，另一个答案似乎有误。位检测应该像这样进行：

b[i / 8] & (1 << (i & 7))

整个更正后的代码如下所示：

typedef unsigned char* bitmap_t;

void set_bitmap(bitmap_t b, int i) {
    b[i / 8] |= 1 << (i & 7);
}

void unset_bitmap(bitmap_t b, int i) {
    b[i / 8] &= ~(1 << (i & 7));
}

int get_bitmap(bitmap_t b, int i) {
    return b[i / 8] & (1 << (i & 7)) ? 1 : 0;
}

bitmap_t create_bitmap(int n) {
    return malloc((n + 7) / 8);
}

- horec

Answer 3

// C++ API
//
#include <iostream>
#include <assert.h>

using namespace std;

class BitSet
{
    public:
        BitSet(int n); 
        ~BitSet();
        bool setBit(int index);
        bool unsetBit(int index);
        char getBit(int index);
        void printBits();

    private:
        unsigned char* m_buffer;
        int m_range;
};

BitSet::BitSet(int n)
{
    m_buffer = (unsigned char*) malloc((n+7)/8);
    assert(m_buffer);
    for (int ii = 0; ii < n; ii++) {
        m_buffer[ii] = 0x00;
    }   
    m_range = n;
}

BitSet::~BitSet()
{
    if (m_buffer) {
        free(m_buffer);
    }   
}

bool
BitSet::setBit(int index)
{
    if (index < 0 || index >= m_range) {
        return false;
    }   

    m_buffer[index/8] = m_buffer[index/8] | ((0x01 << (index%8)));
    return true;
}

bool
BitSet::unsetBit(int index)
{
    if (index < 0 || index >= m_range) {
        return false;
    }   

    m_buffer[index/8] &= ~(0x01 << (index%8));
    return true;
}

char
BitSet::getBit(int index)
{
    if (index < 0 || index >= m_range) {
        return false;
    }

    return (m_buffer[index/8] & (0x01 << (index%8))) ? 0x01 : 0x00;
}

void
BitSet::printBits()
{
    for (int ii = 0; ii < m_range/8; ii++) {
        cout<<"'"<<std::hex<<int(m_buffer[ii])<<"'";
    }
    cout<<endl;
}

- Kanti Varanasi