https://github.com/noporpoise/BitArray/
License: Public Domain, no warranty
Isaac Turner [email protected]
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
To build the library:
make
To build and run the test code:
make test
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"
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.
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)
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)
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)
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);
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 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 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)
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)
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)
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)
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)
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)
}
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)
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)
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)
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 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)
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)
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 / divisordividend = dividend % divisor
Dividend is used to return the remainder.
void bit_array_divide(BIT_ARRAY *dividend, BIT_ARRAY *quotient,
BIT_ARRAY *divisor)
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)
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)
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
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.
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.
Please feel free to submit issues and pull requests. I appreciate bug reports.
Methods are named:
_name()indicates only used internallybit_array_name()exported as is
Testing on different platforms is especially appreciated. I only have access to Mac OS X and Linux.
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
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)