BitArray
C bit array structs and methods
Install / Use
/learn @noporpoise/BitArrayREADME
C code for bit arrays
https://github.com/noporpoise/BitArray/
License: Public Domain, no warranty
Isaac Turner turner.isaac@gmail.com
About
Bit arrays are arrays of bits (values zero or one). This is a convenient and efficient implementation for C/C++. Arrays can be enlarged or shrunk as needed.
Bit arrays are initialised to zero when created or extended. All operations have their bounds checked - an "Out of bounds" error is printed if you try to access a bit with index >= length. Arrays of length 0 are permitted. Indices must be >= 0.
Please get in touch if you have suggestions / requests / bugs.
Adapted from: http://stackoverflow.com/a/2633584/431087
Build
To build the library:
make
To build and run the test code:
make test
Using bit_array in your code
You are welcome to bundle bit_array with your own code. Add to the top of your code:
#include "bit_array.h"
Add to your compiler arguments:
BIT_ARR_PATH=path/to/bit_array/
gcc ... -I$(BIT_ARR_PATH) -L$(BIT_ARR_PATH) -lbitarr
Shorter function names are provided in bar.h, which can be included instead of
bit_array.h:
#include "bar.h"
Thread safety
You cannot safely access the same BitArray in multiple threads at once. Use a lock to protect BitArray objects. The same methods can be safely called in separate threads as long as they are not accessing the same BitArray struct.
Basics
Constructor - create a new bit array of length nbits
BIT_ARRAY* bit_array_create(bit_index_t nbits)
Destructor - free the memory used for a bit array
void bit_array_free(BIT_ARRAY* bitarray)
Alternatively, allocate / free using an existing struct
BIT_ARRAY* bit_array_alloc(BIT_ARRAY* bitarr, bit_index_t nbits)
void bit_array_dealloc(BIT_ARRAY* bitarr)
Get length of bit array
bit_index_t bit_array_length(const BIT_ARRAY* bit_arr)
Change the size of a bit array. Enlarging an array will add zeros to the end of it. Returns 1 on success, 0 on failure (e.g. not enough memory)
char bit_array_resize(BIT_ARRAY* bitarr, bit_index_t new_num_of_bits)
Set/Get bits
Get the value of a bit (returns 0 or 1)
char bit_array_get_bit(const BIT_ARRAY* bitarr, bit_index_t b)
Set a bit (to 1) at position b
void bit_array_set_bit(BIT_ARRAY* bitarr, bit_index_t b)
Clear a bit (to 0) at position b
void bit_array_clear_bit(BIT_ARRAY* bitarr, bit_index_t b)
Toggle a bit. If bit is 0 change to 1; if bit is 1 change to 0. Also known as a complement function.
void bit_array_toggle_bit(BIT_ARRAY* bitarr, bit_index_t b)
Assign a value to a bit. If c != 0 then set bit; otherwise clear bit.
void bit_array_assign_bit(BIT_ARRAY* bitarr, bit_index_t b, char c)
Fast MACROs
You can also use the following which are implemented as MACROs without bounds checking:
bit_array_get(BIT_ARRAY *arr, bit_index_t i)
bit_array_set(BIT_ARRAY *arr, bit_index_t i)
bit_array_clear(BIT_ARRAY *arr, bit_index_t i)
bit_array_toggle(BIT_ARRAY *arr, bit_index_t i)
bit_array_assign(BIT_ARRAY *arr, bit_index_t i, char c)
Get a word_t with the bottom nbits set to 1, the rest to 0:
word_t BIT_MASK(int nbits)
Combine two words with a mask ((a & abits) | (b & ~abits)):
word_t BIT_MASK_MERGE(word_t a, word_t b, int abits)
Set, clear and toggle several bits
Note: variable args are of type unsigned int
Set multiple bits at once.
void bit_array_set_bits(BIT_ARRAY* bitarr, size_t n, ...)
// e.g. set bits 1,20,31:
bit_array_set_bits(bitarr, 3, 1,20,31);
Clear multiple bits at once.
void bit_array_clear_bits(BIT_ARRAY* bitarr, size_t n, ...)
// e.g. clear bits 1,20,31:
bit_array_clear_bits(bitarr, 3, 1,20,31);
Toggle multiple bits at once
void bit_array_toggle_bits(BIT_ARRAY* bitarr, size_t n, ...)
// e.g. toggle bits 1,20,31:
bit_array_toggle_bits(bitarr, 3, 1,20,31);
Set, clear and toggle a region
Clear all the bits in the region start to start+length-1 inclusive
void bit_array_clear_region(BIT_ARRAY* bitarr,
bit_index_t start, bit_index_t length)
Set all the bits in the region start to start+length-1 inclusive
void bit_array_set_region(BIT_ARRAY* bitarr,
bit_index_t start, bit_index_t length)
Toggle all the bits in the region start to start+length-1 inclusive
void bit_array_toggle_region(BIT_ARRAY* bitarr,
bit_index_t start, bit_index_t length)
Set, clear and toggle all bits
Set all bits in this array to 0
void bit_array_clear_all(BIT_ARRAY* bitarr)
Set all bits in this array to 1
void bit_array_set_all(BIT_ARRAY* bitarr)
Set all 1 bits to 0, and all 0 bits to 1 (i.e. flip all the bits)
void bit_array_toggle_all(BIT_ARRAY* bitarr)
Get / set a word
Get a word of a given size. First bit is in the least significant bit position.
Index start must be within the range of the bit array (0 <= x < length)
uint64_t bit_array_get_word64(const BIT_ARRAY* bitarr, bit_index_t start)
uint32_t bit_array_get_word32(const BIT_ARRAY* bitarr, bit_index_t start)
uint16_t bit_array_get_word16(const BIT_ARRAY* bitarr, bit_index_t start)
uint8_t bit_array_get_word8 (const BIT_ARRAY* bitarr, bit_index_t start)
uint64_t bit_array_get_wordn (const BIT_ARRAY* bitarr, bit_index_t start, int n)
Set 64 bits at once from a particular start position
void bit_array_set_word64(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word)
void bit_array_set_word32(BIT_ARRAY* bitarr, bit_index_t start, uint32_t word)
void bit_array_set_word16(BIT_ARRAY* bitarr, bit_index_t start, uint16_t word)
void bit_array_set_word8 (BIT_ARRAY* bitarr, bit_index_t start, uint8_t word)
void bit_array_set_wordn (BIT_ARRAY* bitarr, bit_index_t start, uint64_t word, int n)
Count bits set
Get the number of bits set (hamming weight)
bit_index_t bit_array_num_bits_set(const BIT_ARRAY* bitarr)
Get the number of bits set in on array and not the other. This is equivalent to hamming weight of the XOR of the two arrays. e.g. 10101 vs 00111 => hamming distance 2 (XOR is 10010)
bit_index_t bit_array_hamming_distance(const BIT_ARRAY* arr1,
const BIT_ARRAY* arr2)
Get the number of bits not set (length - hamming weight)
bit_index_t bit_array_num_bits_cleared(const BIT_ARRAY* bitarr)
Find the index of the first bit that is set.
Returns 1 if a bit is set, otherwise 0.
Index of first set bit is stored in the integer pointed to by result.
If no bits are set, value at result is not changed and zero is returned.
char bit_array_find_first_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
Find the index of the first bit that is clear.
Returns 1 if a bit is clear, otherwise 0.
Index of first clear bit is stored in the integer pointed to by result.
If no bits are clear, zero is returned.
char bit_array_find_first_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
Find the index of the last bit that is set.
Returns 1 if a bit is set, otherwise 0.
Index of last set bit is stored in the integer pointed to by result.
If no bits are set, value at result is not changed and zero is returned.
char bit_array_find_last_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
Find the index of the last bit that is NOT set.
Returns 1 if a bit is zero, otherwise 0.
Index of last zero bit is stored in the integer pointed to by result.
If no bits are zero, value at result is not changed and zero is returned.
char bit_array_find_last_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
Find the index of the next bit that is set, at or after offset.
Returns 1 if a bit is set, otherwise 0.
Index of next set bit is stored in the integer pointed to by result.
If no next bit is set, value at result is not changed and 0 is returned.
char bit_array_find_next_set_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
bit_index_t* result)
Find the index of the next bit that is clear, at or after offset.
Returns 1 if a bit is clear, otherwise 0.
Index of next clear bit is stored in the integer pointed to by result.
If no next bit is clear, 0 is returned.
char bit_array_find_next_clear_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
bit_index_t* result)
Find the index of the previous bit that is set, before offset.
Note: 'before' does not include offset.
Returns 1 if a bit is set, otherwise 0
Index of previous set bit is stored in the integer pointed to by result
If no previous bit is set, value at result is not changed
char bit_array_find_prev_set_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
bit_index_t* result)
Find the index of the previous bit that is NOT set, before offset.
Note: 'before' does not include offset.
Returns 1 if a bit is clear, otherwise 0
Index of previous zero bit is stored in the integer pointed to by result
If no previous bit is zero, value at result is not changed
char bit_array_find_prev_clear_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
bit_index_t* result)
Parity / Permutation
Get parity: returns 1 if odd number of bits set, 0 if even.
char bit_array_parity(const BIT_ARRAY* bitarr)
Get the next permutation of an array with a fixed size and given number of bits set. Also known as next lexicographic permutation. Given a bit array find
