Làm cách nào để triển khai mảng bit trong C/Objective C

Question

iOS/Objective-C: Tôi có một mảng lớn các giá trị boolean.

Đây là cách không hiệu quả để lưu trữ các giá trị này - ít nhất tám bit được sử dụng cho mỗi phần tử khi chỉ cần một bit.

Tôi làm cách nào để tối ưu hóa?

Answer 1

thấy CFMutableBitVector/CFBitVector cho một lựa chọn CFType

Answer 2

Bạn sử dụng các phép toán logic bit và dịch chuyển bit. (A tìm kiếm Google cho những điều khoản này có thể cung cấp cho bạn một số ví dụ.)

Về cơ bản bạn khai báo một kiểu số nguyên (bao gồm cả int, char, vv), sau đó bạn "thay đổi" giá trị số nguyên để bit mà bạn muốn, sau đó bạn làm một OR hoặc một AND với số nguyên.

Một số ví dụ minh họa nhanh chóng (trong 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); 
} 

Lưu ý rằng điều này cung cấp "mảng chút" kích thước không đổi (sizeof(int) * 8 bit). Có lẽ điều đó là tốt cho bạn, hoặc có thể bạn sẽ muốn xây dựng một cái gì đó trên đầu trang này. (Hoặc sử dụng lại bất kỳ thư viện nào cung cấp.)

Điều này sẽ sử dụng ít bộ nhớ hơn bool mảng ... Mã trình biên dịch tạo ra để truy cập các bit này sẽ lớn hơn và chậm hơn. Vì vậy, trừ khi bạn có một số lượng lớn các đối tượng cần chứa các mảng bit này, nó có thể có tác động tiêu cực ròng đến cả tốc độ và mức sử dụng bộ nhớ.

Answer 3

Hãy thử điều này:

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

Sau đó, đối với bất kỳ mảng của các yếu tố nguyên unsigned không lớn hơn size_t, các BITOP vĩ mô có thể truy cập vào các mảng như một mảng bit . Ví dụ:

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 */ 

, vv

Answer 4

Tôi đã xem qua câu hỏi này như tôi đang viết một chút khuôn khổ mảng đó là ý định để quản lý một lượng lớn 'bit' tương tự như Java BitSet. Tôi đang tìm xem liệu cái tên mà tôi quyết định có xung đột với các khung Objective-C khác không.

Dù sao, tôi chỉ mới bắt đầu điều này và quyết định xem có đăng nó trên SourceForge hoặc các trang web lưu trữ nguồn mở khác không.

Hãy cho tôi biết nếu bạn quan tâm

Edit: Tôi đã tạo dự án, được gọi là BitArray, trên SourceForge. Nguồn nằm trong kho lưu trữ SF SVN và tôi cũng đã tải lên một khung công tác đã biên dịch. Điều này LINK sẽ nhận được của bạn ở đó.

• Frank

Answer 5

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

sẽ không làm việc ...

Fix:

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