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 the next lexicographic orginisation of the bits Number of possible combinations given by size choose bits_set where bits_set is the result of bit_array_num_bits_set(bitarr). Example: 00011 -> 00101 -> 00110 -> 01001 -> 01010 -> 01100 -> 10001 -> 10010 -> 10100 -> 11000 -> 00011 (back to start)

void bit_array_next_permutation(BIT_ARRAY* bitarr)

Sorting

Put all the 0s before all the 1s

void bit_array_sort_bits(BIT_ARRAY* bitarr)

Put all the 1s before all the 0s

void bit_array_sort_bits_rev(BIT_ARRAY* bitarr)

String and printing functions

To convert to/from string representations of an array, '1' and '0' are used by default as on and off.

Create a bit array from a string of '0's and '1's e.g. "01001010110".

void bit_array_from_str(BIT_ARRAY* bitarr, const char* bitstr)

Construct a BIT_ARRAY from a substring with given on and off characters. left_to_right determines the order in which bits are printed. Terminates string with '\0'.

void bit_array_from_substr(BIT_ARRAY* bitarr, bit_index_t offset,
                           const char* str, size_t len,
                           const char *on, const char *off, char left_to_right)

To string method. Takes a char array to write to. str must be bitarr->num_of_bits+1 in length. Terminates string with '\0'.

char* bit_array_to_str(const BIT_ARRAY* bitarr, char* str)

To construct a string in reverse (highest bit on the left, lowest on the right)

bit_array_to_str_rev(const BIT_ARRAY* bitarr, char* str)

Get a string representations for a given region, using given on/off characters. left_to_right determines the order in which bits are printed. Note: does not null-terminate.

void bit_array_to_substr(const BIT_ARRAY* bitarr,
                         bit_index_t start, bit_index_t length,
                         char* str, char on, char off, char left_to_right)

Print this array to a file stream. Prints '0's and '1'. Doesn't print newline.

void bit_array_print(const BIT_ARRAY* bitarr, FILE* fout)

Print a string representations for a given region, using given on/off characters. left_to_right determines the order in which bits are printed.

void bit_array_print_substr(const BIT_ARRAY* bitarr,
                            bit_index_t start, bit_index_t length,
                            FILE* fout, char on, char off, char left_to_right)

Decimal

Get bit array as decimal str e.g. 0b1101 -> "13". len is the length of str char array. bit_array_to_decimal() write at most len-1 chars to str. Returns the number of characters that would have been written to str -- return is the same as strlen(str) upon success.

size_t bit_array_to_decimal(const BIT_ARRAY *bitarr, char *str, size_t len)

Example usage:

char str[10];
size_t len = bit_array_to_decimal(arr, str, 10);

if(len > 9)
{
  // str wasn't big enough
}

Get bit array from decimal str (e.g. "13" -> 0b1101). Returns number of characters used

size_t bit_array_from_decimal(BIT_ARRAY *bitarr, const char* decimal)

Example usage:

char *str = "1234";
BIT_ARRAY *bitarr = bit_array_create(0);

size_t len = bit_array_from_decimal(bitarr, str);

if(len < strlen(str))
{
  // Parsing ended prematurely (non-numeric characters encountered)
}

Hexidecimal

Loads array from hex string Returns the number of bits loaded (will be chars rounded up to multiple of 8) (0 on failure)

bit_index_t bit_array_from_hex(BIT_ARRAY* bitarr, bit_index_t offset,
                               const char* str, size_t len)

Returns number of characters written

size_t bit_array_to_hex(const BIT_ARRAY* bitarr,
                        bit_index_t start, bit_index_t length,
                        char* str, char uppercase)

Print bit array as hex

size_t bit_array_print_hex(const BIT_ARRAY* bitarr,
                           bit_index_t start, bit_index_t length,
                           FILE* fout, char uppercase)

Clone/copy

Copy a BIT_ARRAY struct and the data it holds - returns pointer to new object

BIT_ARRAY* bit_array_clone(const BIT_ARRAY* bitarr)

Copy bits from one array to another. Destination and source can be the same bit_array and src/dst regions can overlap

void bit_array_copy(BIT_ARRAY* dst, bit_index_t dstindx,
                    const BIT_ARRAY* src, bit_index_t srcindx,
                    bit_index_t length)

Logic operators and shifts

Destination and source bit arrays must be of the same length, however they may point to the same object

void bit_array_and(BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
void bit_array_or(BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
void bit_array_xor(BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
void bit_array_not(BIT_ARRAY* dest, const BIT_ARRAY* src)

Shift array left/right with a given fill (0 or 1)

void bit_array_shift_right(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill)
void bit_array_shift_left(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill)

To shift and add digits instead of losing data, use the extend left shift function:

void bit_array_shift_left_extend(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill)

Circular or cycle shifts. Bits wrap around once shifted off the end

void bit_array_cycle_right(BIT_ARRAY* bitarr, bit_index_t dist)
void bit_array_cycle_left(BIT_ARRAY* bitarr, bit_index_t dist)

Interleave bits

Copy bits from two arrays into another, alternating between taking a bit from each. In other words, two arrays a,b,c,d and 1,2,3,4 -> a,1,b,2,c,3,d,4. Examples:

0011 0000 -> 00001010
1111 0000 -> 10101010
0101 1010 -> 01100110

dst cannot point to the same bit array as src1 or src2. However src1 and src2 may point to the same bit array.

void bit_array_interleave(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)

Reverse

Reverse the whole array or part of it.

void bit_array_reverse(BIT_ARRAY* bitarr)
void bit_array_reverse_region(BIT_ARRAY* bitarr,
                              bit_index_t start, bit_index_t length)

Comparing

Comparison functions return:

0 iff bitarr1 > bitarr2
0 iff bitarr1 == bitarr2
< 0 iff bitarr1 < bitarr2

Compare two bit arrays by value stored, with index 0 being the Least Significant Bit (LSB).

Arrays do not have to be the same length. Example: ..0101 (5) > ...0011 (3) [index 0 is LSB at right hand side].

int bit_array_cmp(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2)

Compare two bit arrays by value stored, with index 0 being the Most Significant Bit (MSB). Sorts on length if all zeros: (0,0) < (0,0,0)

Arrays do not have to be the same length. Example: 10.. > 01.. [index 0 is MSB at left hand side]

int bit_array_cmp_big_endian(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2)

Compare bitarr with (bitarr2 << pos). Does not use array length, only value stored.

int bit_array_cmp_words(const BIT_ARRAY *bitarr,
                        bit_index_t pos, const BIT_ARRAY *bitarr2)

Compare value stored against an unsigned long (treats bitarr as large unsigned integer type):

int bit_array_compare_num(BIT_ARRAY* bitarr, unsigned long value)

Arithmetic

Bit arrays can be interpretted as arbitrarily large unsigned integers. To do this the bit at index 0 is treated as the least significant bit. BitArrays provide functions for arithmetic between a BitArray & a long, and between BitArrays.

Get the value of this number in an unsigned long. Returns 1 on sucess, 0 if value in array is too big.

char bit_array_as_num(BIT_ARRAY* bitarr, unsigned long* result)

(Note: see also bit_array_compare_num(BIT_ARRAY*, unsigned long))

Add to an array. bitarr will be extended if needed.

void bit_array_add_uint64(BIT_ARRAY* bitarr, unsigned long value)

Add add to bitarr at pos -- same as: bitarr + (add << pos) where pos can be bigger than the length of the array (bitarr will be resized)

void bit_array_add_word(BIT_ARRAY *bitarr, bit_index_t pos, uint64_t add)

Add add << pos to bitarr

void bit_array_add_words(BIT_ARRAY *bitarr, bit_index_t pos, BIT_ARRAY *add)

Subtract from an array. If value is greater than bitarr, bitarr is not changed and 0 is returned. Returns 1 on success, 0 if value > bitarr

char bit_array_sub_uint64(BIT_ARRAY* bitarr, unsigned long value)

Minus minus << pos from bitarr

char bit_array_sub_words(BIT_ARRAY* bitarr, bit_index_t pos,
                           BIT_ARRAY* minus)

Multiply by some value

void bit_array_mul_uint64(BIT_ARRAY *bitarr, uint64_t multiplier)

Add two bit arrays together and store the result. src1 and src2 do not have to be the same length. src1, src2 and dst can all be the same or different BIT_ARRAYs. If dst is shorter than either of src1 or src2, it is enlarged to be as long as the longest.

void bit_array_add(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)

Subtract on BIT_ARRAY from another. src1, src2 and dst can all be the same or different BIT_ARRAYs. If dst is shorter than src1, it will be extended to be as long as src1. src1 must be greater than or equal to src2 (src1 >= src2).

void bit_array_subtract(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)

dst = src1 * src2 Pointers cannot all point to the same BIT_ARRAY

void bit_array_multiply(BIT_ARRAY *dst, BIT_ARRAY *src1, BIT_ARRAY *src2)

Divide a BitArray by a BitArray; returns:

quotient = dividend / divisor
dividend = dividend % divisor

Dividend is used to return the remainder.

void bit_array_divide(BIT_ARRAY *dividend, BIT_ARRAY *quotient,
                      BIT_ARRAY *divisor)

Read/Write bit_array to a file

File format is [8 bytes: for number of elements in array][data]. Number of bytes of data is: (int)((num_of_bits + 7) / 8) -- i.e. roundup(num_of_bits/8)

Saves bit array to a file. Returns the number of bytes written

bit_index_t bit_array_save(const BIT_ARRAY* bitarr, FILE* f)

Reads bit array from a file. bitarr is resized and filled with data from the file. Returns 1 on success, 0 on failure.

char bit_array_load(BIT_ARRAY* bitarr, FILE* f)

Hash Value

Get a hash value for this array. Pass seed as 0 on first call, pass previous hash value if rehashing due to a collision. Uses Bob Jenkins hash lookup3 function (http://burtleburtle.net/bob/hash/index.html)

uint64_t bit_array_hash(const BIT_ARRAY* bitarr, uint64_t seed)

Randomness

Set bits randomly with probability prob (where 0 <= prob <= 1)

void bit_array_random(BIT_ARRAY* bitarr, float prob)

Shuffle the bits in an array randomly

void bit_array_shuffle(BIT_ARRAY* bitarr)

// e.g. If you want exactly 9 random bits set in an array, use:
bit_array_set_region(arr, 0, 9); // set the first 9 bits
bit_array_shuffle(arr);          // shuffle the array

Useful functions

The file bit_macros.h contains many useful macros for bit arrays. Simple bit array functions can be implemented with this file alone.

Generalised 'binary to string' function. Adds bits to the string in order of lsb to msb e.g. 0b11010 (26 in decimal) would come out as "01011"

char* bit_array_word2str(const void *ptr, size_t num_of_bits, char *str);

// Same as above but in reverse
char* bit_array_word2str_rev(const void *ptr, size_t num_of_bits, char *str);

For those who hate all that typing: the file "bar.h" contains macros to supply short "bar*" names for the most used bit array operations. This is meant to be similar to the "str*" function names for string manipulation.

Constants

BIT_INDEX_MIN and BIT_INDEX_MAX define the min and max values of datatype bit_index_t. These are defined as 0 and 2^63 - 1.

Contributing

Please feel free to submit issues and pull requests. I appreciate bug reports.

Methods are named:

_name() indicates only used internally
bit_array_name() exported as is

Testing on different platforms is especially appreciated. I only have access to Mac OS X and Linux.

License

This software is in the Public Domain. That means you can do whatever you like with it. That includes being used in proprietary products without attribution or restrictions. There are no warranties and there may be bugs.

Formally we are using CC0 - a Creative Commons license to place this work in the public domain. A copy of CC0 is in the LICENSE file.

"CC0 is a public domain dedication from Creative Commons. A work released
under CC0 is dedicated to the public domain to the fullest extent permitted
by law. If that is not possible for any reason, CC0 also provides a lax,
permissive license as a fallback. Both public domain works and the lax
license provided by CC0 are compatible with the GNU GPL."
  - http://www.gnu.org/licenses/license-list.html#CC0

Development

To do:

search function: int bit_array_search(const BIT_ARRAY *arr, const BIT_ARRAY *query);
windows support
32 bit support
faster multiply / divide? (i.e. Karatsuba)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

C code for bit arrays

About

Build

Using bit_array in your code

Thread safety

Basics

Set/Get bits

Fast MACROs

Set, clear and toggle several bits

Set, clear and toggle a region

Set, clear and toggle all bits

Get / set a word

Count bits set

Parity / Permutation

Sorting

String and printing functions

Decimal

Hexidecimal

Clone/copy

Logic operators and shifts

Interleave bits

Reverse

Comparing

Arithmetic

Read/Write bit_array to a file

Hash Value

Randomness

Useful functions

Constants

Contributing

License

Development

Files

README.md

Latest commit

History

README.md

File metadata and controls

C code for bit arrays

About

Build

Using bit_array in your code

Thread safety

Basics

Set/Get bits

Fast MACROs

Set, clear and toggle several bits

Set, clear and toggle a region

Set, clear and toggle all bits

Get / set a word

Count bits set

Parity / Permutation

Sorting

String and printing functions

Decimal

Hexidecimal

Clone/copy

Logic operators and shifts

Interleave bits

Reverse

Comparing

Arithmetic

Read/Write bit_array to a file

Hash Value

Randomness

Useful functions

Constants

Contributing

License

Development