logo标签列表

能否使用位域数组？

c++carraysstructbit-fields
31

我很好奇，是否可以使用位域数组？ 比如：

struct st
{
  unsigned int i[5]: 4;
};
3
请注意，大多数最近的 C 代码不再使用位域。一种有用的替代方法是使用位掩码字段，并对它们执行位运算。顺便说一句，编译器会生成等效的代码。 - Basile Starynkevitch
7
@BasileStarynkevitch说："我想知道你是从哪里得到这个观点的。使用位域比使用位运算处理位掩码字段要容易出错得多。" - chqrlie
4个回答
27

不可以。位域只能与整数类型的变量一起使用。

C11-§6.7.2.1/5

位域应该具有的类型是限定或未限定版本的_Bool、signed int、unsigned int或其他某个实现定义类型。

或者您可以这样做。

struct st
{
    unsigned int i: 4;  
} arr_st[5];

但它的大小将是一个具有5个成员，每个成员都有4位位域的struct大小的5倍（在@Jonathan Leffler的评论中提到）。所以，在这里它没有太多意义。

更接近你可以这样做

struct st
{
    uint8_t i: 4;   // Will take only a byte
} arr_st[5];
8
但是这个 struct st {unsigned int i: 4;} arr_st[5]; 的大小很可能是 unsigned int 的5倍，它不会只有20位长。 - Jonathan Leffler
@JonathanLeffler; 是的。但没有其他方法来声明一个位域数组。 - haccks
@haccks 谢谢你的帮助。 - msc
可能无法使用uint8_t类型。使用struct st { unsigned char i: 4; } arr_st[5];或者unsigned char arr[5];似乎更可取。 - chqrlie
1
@IlmariKaronen；我的意思是说，结构体arr_st将会是结构体struct stt的5倍，例如：struct stt { unsigned int i: 4; unsigned int j: 4; unsigned int k: 4; unsigned int l: 4; unsigned int m: 4; } s; - haccks
10

C不支持位域数组，所以简短的回答是不支持。

对于非常大的数组，将值打包为每个字节的2个值可能是值得的：

#define ARRAY_SIZE  1000000

unsigned char arr[(ARRAY_SIZE + 1) / 2];

int get_4bits(const unsigned char *arr, size_t index) {
    return arr[index >> 1] >> ((index & 1) << 2);
}

int set_4bits(unsigned char *arr, size_t index, int value) {
    arr[index >> 1] &= ~ 0x0F << ((index & 1) << 2);
    arr[index >> 1] |= (value & 0x0F) << ((index & 1) << 2);
}
7

您可以针对这种情况编写自己的类。例如：

template <typename T, size_t ITEM_BIT_SIZE>
class BitArrayView {
private:
    static const size_t ARRAY_ENTRY_BITS = sizeof(T) * 8;
    static const T ITEM_MASK = (~((T) 0)) >> (ARRAY_ENTRY_BITS - ITEM_BIT_SIZE);
    T* arr;
public:
    struct ItemMutator {
        BitArrayView* owner;
        size_t index;
        T operator=(T value) {
            return owner->set(index, value);
        }
        operator T() {
            return owner->get(index);
        }
    };
    const size_t bitSize;
    BitArrayView(T* arr, size_t length) : arr(arr), bitSize((length * ARRAY_ENTRY_BITS) / ITEM_BIT_SIZE) {}
    T get(size_t index) const {
        size_t bitPos = index * ITEM_BIT_SIZE;
        size_t arrIndex = bitPos / ARRAY_ENTRY_BITS;
        size_t shiftCount = bitPos % ARRAY_ENTRY_BITS;
        return (arr[arrIndex] >> shiftCount) & ITEM_MASK;
    }
    T set(size_t index, T value) {
        size_t bitPos = index * ITEM_BIT_SIZE;
        size_t arrIndex = bitPos / ARRAY_ENTRY_BITS;
        size_t shiftCount = bitPos % ARRAY_ENTRY_BITS;
        value &= ITEM_MASK; // trim
        arr[arrIndex] &= ~(ITEM_MASK << shiftCount); // clear target bits
        arr[arrIndex] |= value << shiftCount; // insert new bits 
        return value;
    }
    ItemMutator operator[](size_t index) {
        return { this, index };
    }
};

然后您可以像“位域”数组一样访问它：

// create array of some uints
unsigned int arr[5] = { 0, 0, 0, 0, 0 };

// set BitArrayView of 3-bit entries on some part of the array 
// (two indexes starting at 1)
BitArrayView<unsigned int, 3> arrView(arr + 1, 2);

// should equal 21 now => (2 * 32) / 3
arrView.bitSize == 21;

for (unsigned int i = 0; i < arrView.bitSize; i++) {
    arrView[i] = 7; // eg.: 0b111;
}

// now arr[1] should have all bits set
// and arr[2] should have all bits set but last one unset => (2 * 32) % 3 = 1
// the remaining arr items should stay untouched

这是一个简单的实现，仅适用于无符号后备数组。

注意在 operator[] 中的 "mutator trick" ;)。

当然也可以实现其他操作符。

编辑（在Josh Klodnicki的评论之后）

实际上它包含了一个错误，当 "位块" 部分重叠实际数组条目时会出现。下面是一个修复方法（但它有点丑陋 ;) ）。

template <typename T, size_t ITEM_BIT_SIZE>
class BitArrayView {
private:
    static const size_t ARRAY_ENTRY_BITS = sizeof(T) * 8;
    T* arr;

public:
    struct ItemMutator {
        BitArrayView* owner;
        size_t index;
        ItemMutator& operator=(T value) {
            owner->set(index, value);
            return *this;
        }
        operator T() {
            return owner->get(index);
        }
    };

    const size_t bitSize;
    BitArrayView(T* arr, size_t length) : arr(arr), bitSize((length* ARRAY_ENTRY_BITS) / ITEM_BIT_SIZE) {}

    T get(size_t index) const {
        T value = 0;
        int pos = 0;
        size_t bitPos = index * ITEM_BIT_SIZE;
        size_t arrIndex = bitPos / ARRAY_ENTRY_BITS;
        size_t readPos = bitPos % ARRAY_ENTRY_BITS;
        size_t bitCount = ITEM_BIT_SIZE;
        if (readPos > 0) {
            int chunkLength = ARRAY_ENTRY_BITS - readPos;
            if (bitCount < chunkLength) {
                value = (((arr[arrIndex] >> readPos) & ((1u << bitCount) - 1)));
                readPos += bitCount;
                return value;
            }
            value = (((arr[arrIndex] >> readPos) & ((1u << chunkLength) - 1)));
            ++arrIndex;
            readPos = 0;
            pos = chunkLength;
            bitCount -= chunkLength;
        }
        while (bitCount >= ARRAY_ENTRY_BITS) {
            value |= (arr[arrIndex++] << pos);
            pos += ARRAY_ENTRY_BITS;
            bitCount -= ARRAY_ENTRY_BITS;
        }
        if (bitCount > 0) {
            value |= ((arr[arrIndex] & ((1u << bitCount) - 1)) << pos);
        }
        return value;
    }

    void set(size_t index, T value) {
        size_t bitPos = index * ITEM_BIT_SIZE;
        size_t arrIndex = bitPos / ARRAY_ENTRY_BITS;
        size_t writePos = bitPos % ARRAY_ENTRY_BITS;
        size_t bitCount = ITEM_BIT_SIZE;

        if (writePos > 0) {
            int chunkLength = ARRAY_ENTRY_BITS - writePos;
            if (bitCount < chunkLength) {
                auto mask = (((1u << bitCount) - 1) << writePos);
                arr[arrIndex] = (arr[arrIndex] ^ ((arr[arrIndex] ^ (value << writePos)) & mask));
                writePos += bitCount;
                return;
            }
            auto mask = (((1u << chunkLength) - 1) << writePos);
            arr[arrIndex] = (arr[arrIndex] ^ ((arr[arrIndex] ^ (value << writePos)) & mask));
            ++arrIndex;
            writePos = 0;
            value >>= chunkLength;
            bitCount -= chunkLength;
        }
        while (bitCount >= ARRAY_ENTRY_BITS) {
            arr[arrIndex++] = value;
            value >>= ARRAY_ENTRY_BITS;
            bitCount -= ARRAY_ENTRY_BITS;
        }
        if (bitCount > 0) {
            auto mask = ((1u << bitCount) - 1);
            arr[arrIndex] = (arr[arrIndex] ^ ((arr[arrIndex] ^ value) & mask));
        }
    }

    ItemMutator operator[](size_t index) {
        return { this, index };
    }
};

现在已经不再简单了，下面我放置了一个简单的位数组实现，可以单独访问单个位。

template<size_t SIZE>
class BitArray {
private:
    static constexpr const size_t CELL_SIZE = sizeof(unsigned) * 8;
    static constexpr const size_t ARR_SIZE = (SIZE + CELL_SIZE) / CELL_SIZE;
    unsigned arr[ARR_SIZE];
public:
    class BitMutator {
    private:
        unsigned& cellRef;
        const size_t bitPos;

    public:
        BitMutator(unsigned& cellRef, size_t bitPos) : cellRef(cellRef), bitPos(bitPos) {}
        BitMutator(const BitMutator& source) = default;
        BitMutator(BitMutator&& source) = default;

        BitMutator& operator=(unsigned value) {
            cellRef &= ~(1u << bitPos);
            cellRef |= ((value & 1u) << bitPos);
            return *this;
        }
        operator unsigned() const {
            return (cellRef >> bitPos) & 1u;
        }
    };

    BitArray() : arr{0} {};

    BitMutator operator[](size_t index) {
        return BitMutator(arr[index / CELL_SIZE], index % CELL_SIZE);
    }

    size_t size() const {
        return SIZE;
    }

    size_t arr_size() const {
        return ARR_SIZE;
    }

    operator unsigned* () {
        return arr;
    }
};

void testBitArray() {
    BitArray<21> bitArr;

    for (int i = 0; i < bitArr.size(); i++) {
        bitArr[i] = i % 2;
    }

    for (int i = 0; i < bitArr.size(); i++) {
        std::cout << bitArr[i] << ", ";
    }

    unsigned* backing_array = (unsigned*) bitArr;
    size_t backing_arr_size = bitArr.arr_size();

    for (int i = 0; i < backing_arr_size; i++) {
        std::cout << backing_array[i] << ", ";
    }
}
该实现没有考虑重叠数组条目的“字段”。在此示例中，arrView[10] 应访问 arr[1]{30-31} 和 arr[2]{0}，但按照现有编写方式，它并没有这样做。 - Josh Klodnicki
1
@JoshKlodnicki 你说得对，我会修复并编辑答案。 - Tomasz Gawel
@JoshKlodnicki 我提供了一个修复后的版本，以及一个简单的BItArray实现（在我的更改后，原始的BitArrayView似乎过于复杂）。 - Tomasz Gawel
0
不，位域只支持整数类型。但是对于非常小的数组，您可以将每个元素作为单独的属性存储，例如：
struct st
{
  unsigned int i0: 1;
  unsigned int i1: 1;
  unsigned int i2: 1;
  unsigned int i3: 1;
  unsigned int i4: 1;
};

这种方法的缺点显然是，您不能再使用基于数组的操作或方法，例如运行时索引，但对于像数学向量这样的基本应用程序来说，它已经足够好了。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接