我很想知道,是否可以使用位字段数组?喜欢:
struct st
{
unsigned int i[5]: 4;
};
不,你不能。位域只能与整型变量一起使用。
位字段的类型应为
、_Bool
、signed int
的限定或非限定版本,或某些其他实现定义的类型。unsigned int
或者你也可以这样做
struct st
{
unsigned int i: 4;
} arr_st[5];
但其大小将是
struct
大小的 5 倍(如 @Jonathan Leffler 的 comment 中所述),其中每个成员都有 5 个位字段 4
。所以,这里没有多大意义。
你可以更仔细地做到这一点
struct st
{
uint8_t i: 4; // Will take only a byte
} arr_st[5];
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);
}
您可以为此案例编写自己的类。例如:
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[]
中的“变异技巧”;)。
当然也可以实现一些其他运算符。
编辑(乔希·克洛德尼基评论后)
它实际上包含一个错误,当“位块”与部分实际数组条目重叠时就会出现该错误。这是一个修复(但有点难看;))。
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] << ", ";
}
}
不,位域仅支持整型。但对于非常小的数组,您可以将每个元素单独存储为属性,例如:
struct st
{
unsigned int i0: 1;
unsigned int i1: 1;
unsigned int i2: 1;
unsigned int i3: 1;
unsigned int i4: 1;
};
这种方法的缺点显然是您不能再使用基于数组的操作或方法,例如运行时索引,但它对于数学向量等基本应用程序来说已经足够好了。
我不知道这是否是你想要的,但你可以这样做。
typedef unsigned long long ui64;
template<int BW> struct tblcnt{
tblcnt() : m(0) {}
ui64 operator[](int a){ return (m>>kArr[a]) & kMsk; }
const ui64 kMsk = ((1<<BW)-1), kArr[16] = {0,BW,2*BW,3*BW,4*BW,5*BW,6*BW,7*BW,8*BW,9*BW,10*BW,11*BW,12*BW,13*BW,14*BW,15*BW};
void operator++(){m++;}
ui64 m;
};
Godbolt 告诉我它能够产生一个转变 和 且具有常数。现在这段代码 [] 只会给我们一个 getter。您可以使用以类似方式编码的 setter 来补充它。并使用反向移位掩码,或使用移位值进行运算。我们可以根据模板参数 BW 类似地定义这些内容,以便编译器可以生成最佳的汇编代码。
如果您使用较新的 C++ 标准之一,您可以使用 int 数组作为模板参数并相应地定义 kArr。 {0,BW[0],BW[0]+BW[1],...}。您仍然可以让它生成最佳代码。
即使您不使用更高版本的 C++ 标准(C++11 及更高版本),您也可以在此处的答案中使用“pythonic”:s 方法:将数组作为模板类型传递