如何在 C/Objective C 中实现位数组

Question

iOS / Objective-C：我有大量布尔值。

这是存储这些值的一种低效方式——当只需要一个元素时，每个元素至少使用八位。

我该如何优化？

Answer 1

请参阅 CFMutableBitVector/CFBitVector 了解 CFType 选项

Answer 2

试试这个：

#define BITOP(a,b,op) \
 ((a)[(size_t)(b)/(8*sizeof *(a))] op ((size_t)1<<((size_t)(b)%(8*sizeof *(a)))))

然后，对于任何不大于 size_t 的无符号整数元素数组，BITOP 宏可以将数组作为位数组进行访问。例如：

unsigned char array[16] = {0};
BITOP(array, 40, |=); /* sets bit 40 */
BITOP(array, 41, ^=); /* toggles bit 41 */
if (BITOP(array, 42, &)) return 0; /* tests bit 42 */
BITOP(array, 43, &=~); /* clears bit 43 */

等等。

Answer 3

您使用按位逻辑运算和位移位。 （Google 搜索这些术语可能会给您一些示例。）

基本上，您声明一个整数类型（包括 int、char 等），然后“移位”整数值到您想要的位，然后与该整数执行“或”或“与”操作。

一些快速说明性示例（C++ 语言）：

inline bool bit_is_on(int bit_array, int bit_number)
{
   return ((bit_array) & (1 << bit_number)) ? true : false;
}

inline void set_bit(int &bit_array, int bit_number)
{
   bit_array |= (1 << bit_number);
}

inline void clear_bit(int &bit_array, int bit_number)
{
   bit_array &= ~(1 << bit_number);
}

请注意，这提供了恒定大小（sizeof(int) * 8 位）的“位数组”。也许这对你来说没问题，或者你可能想在此基础上构建一些东西。 （或者重新使用某些库提供的任何内容。）

这将使用比 bool 数组更少的内存...但是...编译器生成的用于访问这些位的代码将更大且更慢。因此，除非您有大量需要包含这些位数组的对象，否则它可能会对速度和内存使用产生净负面影响。

Answer 4

#define BITOP(a,b,op) \
   ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a))))

不起作用...

修复：

#define BITOP(a,b,op) \
 ((a)[(size_t)(b)/(8*sizeof *(a))] op ((size_t)1<<((size_t)(b)%(8*sizeof *(a)))))

Answer 5

我在编写一个位数组框架时遇到了这个问题，该框架旨在管理类似于 Java BitSet 的大量“位”。我想看看我决定的名称是否与其他 Objective-C 框架冲突。

不管怎样，我才刚刚开始，正在决定是否将其发布到 SourceForge 或其他开源托管网站上。

如果您有兴趣，请告诉我

编辑：我已经在 SourceForge 上创建了名为 BitArray 的项目。源代码位于 SF SVN 存储库中，我还上传了编译后的框架。这个LINK将帮助您到达那里。

• 坦率