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

Question

iOS/Objective-C:我有一大堆布尔值.

这是存储这些值的低效方法 - 当只需要一个时,每个元素至少使用8位.

我该如何优化？

Answer 1

有关CFType选项,请参阅CFMutableBitVector/CFBitVector

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

您使用按位逻辑运算和位移.(谷歌搜索这些术语可能会给你一些例子.)

基本上你声明一个整数类型(包括int,char等),然后你将整数值"移位"到你想要的位,然后你用整数做一个OR或AND.

一些快速说明性示例(在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数组更少的内存...但是......编译器生成的用于访问这些位的代码将更大更慢.因此,除非您有大量需要包含这些位数组的对象,否则它可能会对速度和内存使用产生净负面影响.