bit_array.h 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552
  1. /*
  2. bit_array.h
  3. project: bit array C library
  4. url: https://github.com/noporpoise/BitArray/
  5. maintainer: Isaac Turner <turner.isaac@gmail.com>
  6. license: Public Domain, no warranty
  7. date: Sep 2014
  8. */
  9. #ifndef BIT_ARRAY_HEADER_SEEN
  10. #define BIT_ARRAY_HEADER_SEEN
  11. #include <stdio.h>
  12. #include <inttypes.h>
  13. #include "bit_macros.h"
  14. typedef struct BIT_ARRAY BIT_ARRAY;
  15. // 64 bit words
  16. typedef uint64_t word_t, word_addr_t, bit_index_t;
  17. typedef uint8_t word_offset_t; // Offset within a 64 bit word
  18. #define BIT_INDEX_MIN 0
  19. #define BIT_INDEX_MAX (~(bit_index_t)0)
  20. #ifdef __cplusplus
  21. extern "C" {
  22. #endif
  23. //
  24. // Structs
  25. //
  26. struct BIT_ARRAY
  27. {
  28. word_t* words;
  29. bit_index_t num_of_bits;
  30. // Number of words used -- this is just round_up(num_of_bits / 64)
  31. // if num_of_bits == 0, this is 0
  32. word_addr_t num_of_words;
  33. // For more efficient allocation we use realloc only to double size --
  34. // not for adding every word. Initial size is INIT_CAPACITY_WORDS.
  35. word_addr_t capacity_in_words;
  36. };
  37. //
  38. // Basics: Constructor, destructor, get length, resize
  39. //
  40. // Constructor - create a new bit array of length nbits
  41. BIT_ARRAY* bit_array_create(bit_index_t nbits);
  42. // Destructor - free the memory used for a bit array
  43. void bit_array_free(BIT_ARRAY* bitarray);
  44. // Allocate using existing struct
  45. BIT_ARRAY* bit_array_alloc(BIT_ARRAY* bitarr, bit_index_t nbits);
  46. void bit_array_dealloc(BIT_ARRAY* bitarr);
  47. // Get length of bit array
  48. bit_index_t bit_array_length(const BIT_ARRAY* bit_arr);
  49. // Change the size of a bit array. Enlarging an array will add zeros
  50. // to the end of it. Returns 1 on success, 0 on failure (e.g. not enough memory)
  51. char bit_array_resize(BIT_ARRAY* bitarr, bit_index_t new_num_of_bits);
  52. // If bitarr length < num_bits, resizes to num_bits
  53. char bit_array_ensure_size(BIT_ARRAY* bitarr, bit_index_t ensure_num_of_bits);
  54. // Same as above but exit with an error message if out of memory
  55. void bit_array_resize_critical(BIT_ARRAY* bitarr, bit_index_t num_of_bits);
  56. void bit_array_ensure_size_critical(BIT_ARRAY* bitarr, bit_index_t num_of_bits);
  57. //
  58. // Macros
  59. //
  60. //
  61. // Get, set, clear, assign and toggle individual bits
  62. // Macros for fast access -- beware: no bounds checking
  63. //
  64. #define bit_array_get(arr,i) bitset_get((arr)->words, i)
  65. #define bit_array_set(arr,i) bitset_set((arr)->words, i)
  66. #define bit_array_clear(arr,i) bitset_del((arr)->words, i)
  67. #define bit_array_toggle(arr,i) bitset_tgl((arr)->words, i)
  68. // c must be 0 or 1
  69. #define bit_array_assign(arr,i,c) bitset_cpy((arr)->words,i,c)
  70. //
  71. // Get, set, clear, assign and toggle individual bits
  72. // "Safe": use assert() to check bounds
  73. //
  74. // Get the value of a bit (returns 0 or 1)
  75. char bit_array_get_bit(const BIT_ARRAY* bitarr, bit_index_t b);
  76. void bit_array_set_bit(BIT_ARRAY* bitarr, bit_index_t b);
  77. void bit_array_clear_bit(BIT_ARRAY* bitarr, bit_index_t b);
  78. void bit_array_toggle_bit(BIT_ARRAY* bitarr, bit_index_t b);
  79. // If char c != 0, set bit; otherwise clear bit
  80. void bit_array_assign_bit(BIT_ARRAY* bitarr, bit_index_t b, char c);
  81. //
  82. // "Resizing": enlarge array if needed
  83. //
  84. char bit_array_rget(BIT_ARRAY* bitarr, bit_index_t b);
  85. void bit_array_rset(BIT_ARRAY* bitarr, bit_index_t b);
  86. void bit_array_rclear(BIT_ARRAY* bitarr, bit_index_t b);
  87. void bit_array_rtoggle(BIT_ARRAY* bitarr, bit_index_t b);
  88. void bit_array_rassign(BIT_ARRAY* bitarr, bit_index_t b, char c);
  89. //
  90. // Set, clear and toggle several bits at once
  91. //
  92. // Set multiple bits at once.
  93. // e.g. set bits 1, 20 & 31: bit_array_set_bits(bitarr, 3, 1,20,31);
  94. // Note: variable args are of type unsigned int
  95. void bit_array_set_bits(BIT_ARRAY* bitarr, size_t n, ...);
  96. // Clear multiple bits at once.
  97. // e.g. clear bits 1, 20 & 31: bit_array_clear_bits(bitarr, 3, 1,20,31);
  98. // Note: variable args are of type unsigned int
  99. void bit_array_clear_bits(BIT_ARRAY* bitarr, size_t n, ...);
  100. // Toggle multiple bits at once
  101. // e.g. toggle bits 1, 20 & 31: bit_array_toggle_bits(bitarr, 3, 1,20,31);
  102. // Note: variable args are of type unsigned int
  103. void bit_array_toggle_bits(BIT_ARRAY* bitarr, size_t n, ...);
  104. //
  105. // Set, clear and toggle all bits in a region
  106. //
  107. // Set all the bits in a region
  108. void bit_array_set_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len);
  109. // Clear all the bits in a region
  110. void bit_array_clear_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len);
  111. // Toggle all the bits in a region
  112. void bit_array_toggle_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len);
  113. //
  114. // Set, clear and toggle all bits at once
  115. //
  116. // Set all bits in this array to 1
  117. void bit_array_set_all(BIT_ARRAY* bitarr);
  118. // Set all bits in this array to 0
  119. void bit_array_clear_all(BIT_ARRAY* bitarr);
  120. // Set all 1 bits to 0, and all 0 bits to 1
  121. void bit_array_toggle_all(BIT_ARRAY* bitarr);
  122. //
  123. // Get / set a word of a given size
  124. //
  125. // First bit is in the least significant bit position
  126. // start index must be within the range of the bit array (0 <= x < length)
  127. uint64_t bit_array_get_word64(const BIT_ARRAY* bitarr, bit_index_t start);
  128. uint32_t bit_array_get_word32(const BIT_ARRAY* bitarr, bit_index_t start);
  129. uint16_t bit_array_get_word16(const BIT_ARRAY* bitarr, bit_index_t start);
  130. uint8_t bit_array_get_word8(const BIT_ARRAY* bitarr, bit_index_t start);
  131. uint64_t bit_array_get_wordn(const BIT_ARRAY* bitarr, bit_index_t start, int n);
  132. // Set 64 bits at once from a particular start position
  133. void bit_array_set_word64(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word);
  134. void bit_array_set_word32(BIT_ARRAY* bitarr, bit_index_t start, uint32_t word);
  135. void bit_array_set_word16(BIT_ARRAY* bitarr, bit_index_t start, uint16_t word);
  136. void bit_array_set_word8(BIT_ARRAY* bitarr, bit_index_t start, uint8_t byte);
  137. void bit_array_set_wordn(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word, int n);
  138. //
  139. // Number of bits set
  140. //
  141. // Get the number of bits set (hamming weight)
  142. bit_index_t bit_array_num_bits_set(const BIT_ARRAY* bitarr);
  143. // Get the number of bits not set (length - hamming weight)
  144. bit_index_t bit_array_num_bits_cleared(const BIT_ARRAY* bitarr);
  145. // Get the number of bits set in on array and not the other. This is equivalent
  146. // to hamming weight of the XOR when the two arrays are the same length.
  147. // e.g. 10101 vs 00111 => hamming distance 2 (XOR is 10010)
  148. bit_index_t bit_array_hamming_distance(const BIT_ARRAY* arr1,
  149. const BIT_ARRAY* arr2);
  150. // Parity - returns 1 if odd number of bits set, 0 if even
  151. char bit_array_parity(const BIT_ARRAY* bitarr);
  152. //
  153. // Find indices of set/clear bits
  154. //
  155. // Find the index of the next bit that is set, at or after `offset`
  156. // Returns 1 if a bit is set, otherwise 0
  157. // Index of next set bit is stored in the integer pointed to by result
  158. // If no next bit is set result is not changed
  159. char bit_array_find_next_set_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
  160. bit_index_t* result);
  161. // Find the index of the next bit that is NOT set, at or after `offset`
  162. // Returns 1 if a bit is NOT set, otherwise 0
  163. // Index of next zero bit is stored in the integer pointed to by `result`
  164. // If no next bit is zero, value at `result` is not changed
  165. char bit_array_find_next_clear_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
  166. bit_index_t* result);
  167. // Find the index of the previous bit that is set, before offset.
  168. // Returns 1 if a bit is set, otherwise 0
  169. // Index of previous set bit is stored in the integer pointed to by `result`
  170. // If no previous bit is set result is not changed
  171. char bit_array_find_prev_set_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
  172. bit_index_t* result);
  173. // Find the index of the previous bit that is NOT set, before offset.
  174. // Returns 1 if a bit is clear, otherwise 0
  175. // Index of previous zero bit is stored in the integer pointed to by `result`
  176. // If no previous bit is zero result is not changed
  177. char bit_array_find_prev_clear_bit(const BIT_ARRAY* bitarr, bit_index_t offset,
  178. bit_index_t* result);
  179. // Find the index of the first bit that is set.
  180. // Returns 1 if a bit is set, otherwise 0
  181. // Index of first set bit is stored in the integer pointed to by `result`
  182. // If no bit is set result is not changed
  183. char bit_array_find_first_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result);
  184. // Find the index of the first bit that is NOT set.
  185. // Returns 1 if a bit is clear, otherwise 0
  186. // Index of first zero bit is stored in the integer pointed to by `result`
  187. // If no bit is zero result is not changed
  188. char bit_array_find_first_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result);
  189. // Find the index of the last bit that is set.
  190. // Returns 1 if a bit is set, otherwise 0
  191. // Index of last set bit is stored in the integer pointed to by `result`
  192. // If no bit is set result is not changed
  193. char bit_array_find_last_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result);
  194. // Find the index of the last bit that is NOT set.
  195. // Returns 1 if a bit is clear, otherwise 0
  196. // Index of last zero bit is stored in the integer pointed to by `result`
  197. // If no bit is zero result is not changed
  198. char bit_array_find_last_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result);
  199. //
  200. // Sorting
  201. //
  202. // Put all the 0s before all the 1s
  203. void bit_array_sort_bits(BIT_ARRAY* bitarr);
  204. // Put all the 1s before all the 0s
  205. void bit_array_sort_bits_rev(BIT_ARRAY* bitarr);
  206. //
  207. // String and printing methods
  208. //
  209. // Construct a BIT_ARRAY from a string.
  210. void bit_array_from_str(BIT_ARRAY* bitarr, const char* bitstr);
  211. // Construct a BIT_ARRAY from a substring with given on and off characters.
  212. void bit_array_from_substr(BIT_ARRAY* bitarr, bit_index_t offset,
  213. const char* str, size_t len,
  214. const char *on, const char *off, char left_to_right);
  215. // Takes a char array to write to. `str` must be bitarr->num_of_bits+1 in
  216. // length. Terminates string with '\0'
  217. char* bit_array_to_str(const BIT_ARRAY* bitarr, char* str);
  218. char* bit_array_to_str_rev(const BIT_ARRAY* bitarr, char* str);
  219. // Get a string representations for a given region, using given on/off
  220. // characters.
  221. // Note: does not null-terminate
  222. void bit_array_to_substr(const BIT_ARRAY* bitarr,
  223. bit_index_t start, bit_index_t length,
  224. char* str, char on, char off, char left_to_right);
  225. // Print this array to a file stream. Prints '0's and '1'. Doesn't print
  226. // newline.
  227. void bit_array_print(const BIT_ARRAY* bitarr, FILE* fout);
  228. // Print a string representations for a given region, using given on/off
  229. // characters. Reverse prints from highest to lowest -- this is useful for
  230. // printing binary numbers
  231. void bit_array_print_substr(const BIT_ARRAY* bitarr,
  232. bit_index_t start, bit_index_t length,
  233. FILE* fout, char on, char off, char left_to_right);
  234. //
  235. // Decimal
  236. //
  237. // Get bit array as decimal str (e.g. 0b1101 -> "13")
  238. size_t bit_array_to_decimal(const BIT_ARRAY *bitarr, char *str, size_t len);
  239. // Return number of characters used
  240. size_t bit_array_from_decimal(BIT_ARRAY *bitarr, const char* decimal);
  241. //
  242. // Hexidecimal
  243. //
  244. // Loads array from hex string
  245. // Returns the number of bits loaded (will be chars rounded up to multiple of 8)
  246. // (0 on failure)
  247. bit_index_t bit_array_from_hex(BIT_ARRAY* bitarr, bit_index_t offset,
  248. const char* str, size_t len);
  249. // Returns number of characters written
  250. size_t bit_array_to_hex(const BIT_ARRAY* bitarr,
  251. bit_index_t start, bit_index_t length,
  252. char* str, char uppercase);
  253. // Print bit array as hex
  254. size_t bit_array_print_hex(const BIT_ARRAY* bitarr,
  255. bit_index_t start, bit_index_t length,
  256. FILE* fout, char uppercase);
  257. //
  258. // Clone and copy
  259. //
  260. // Copy a BIT_ARRAY struct and the data it holds - returns pointer to new object
  261. #define bit_array_dup bit_array_clone
  262. BIT_ARRAY* bit_array_clone(const BIT_ARRAY* bitarr);
  263. // Copy bits from one array to another
  264. // Note: use MACRO bit_array_copy
  265. // Destination and source can be the same bit_array and
  266. // src/dst regions can overlap
  267. void bit_array_copy(BIT_ARRAY* dst, bit_index_t dstindx,
  268. const BIT_ARRAY* src, bit_index_t srcindx,
  269. bit_index_t length);
  270. // copy all of src to dst. dst is resized to match src.
  271. void bit_array_copy_all(BIT_ARRAY* dst, const BIT_ARRAY* src);
  272. //
  273. // Logic operators
  274. //
  275. // BIT_ARRAYs can all be different or the same object
  276. // dest array will be resized if it is too short
  277. //
  278. void bit_array_and(BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2);
  279. void bit_array_or (BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2);
  280. void bit_array_xor(BIT_ARRAY* dest, const BIT_ARRAY* src1, const BIT_ARRAY* src2);
  281. void bit_array_not(BIT_ARRAY* dest, const BIT_ARRAY* src);
  282. //
  283. // Comparisons
  284. //
  285. // Note: (bit_array_cmp(a,b) == 0) <=> (bit_array_cmp_big_endian(a,b) == 0)
  286. // comparison functions return:
  287. // 1 iff bitarr1 > bitarr2
  288. // 0 iff bitarr1 == bitarr2
  289. // -1 iff bitarr1 < bitarr2
  290. // Compare two bit arrays by value stored, with index 0 being the Least
  291. // Significant Bit (LSB). Arrays do not have to be the same length.
  292. // Example: ..0101 (5) > ...0011 (3) [index 0 is LSB at right hand side]
  293. int bit_array_cmp(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2);
  294. // Compare two bit arrays by value stored, with index 0 being the Most
  295. // Significant Bit (MSB). Arrays do not have to be the same length.
  296. // Example: 10.. > 01.. [index 0 is MSB at left hand side]
  297. int bit_array_cmp_big_endian(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2);
  298. // compare bitarr with (bitarr2 << pos)
  299. int bit_array_cmp_words(const BIT_ARRAY *bitarr,
  300. bit_index_t pos, const BIT_ARRAY *bitarr2);
  301. //
  302. // Shift, interleave, reverse
  303. //
  304. // Shift array left/right. If fill is zero, filled with 0, otherwise 1
  305. void bit_array_shift_right(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill);
  306. void bit_array_shift_left (BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill);
  307. // shift left without losing any bits. Resizes bitarr.
  308. void bit_array_shift_left_extend(BIT_ARRAY* bitarr, bit_index_t shift_dist,
  309. char fill);
  310. // Cyclic shift
  311. void bit_array_cycle_right(BIT_ARRAY* bitarr, bit_index_t dist);
  312. void bit_array_cycle_left (BIT_ARRAY* bitarr, bit_index_t dist);
  313. // Interleave
  314. // dst cannot point to the same bit array as src1 or src2
  315. // src1, src2 may point to the same bit array
  316. // abcd 1234 -> a1b2c3d4
  317. // 0011 0000 -> 00001010
  318. // 1111 0000 -> 10101010
  319. // 0101 1010 -> 01100110
  320. // Extends dst if it is too short, but does not shrink it if it is too long
  321. // if dst is longer than length(src1)+length(src2), the end bits are not altered
  322. void bit_array_interleave(BIT_ARRAY* dst,
  323. const BIT_ARRAY* src1,
  324. const BIT_ARRAY* src2);
  325. // Reverse the whole array or part of it
  326. void bit_array_reverse(BIT_ARRAY* bitarr);
  327. void bit_array_reverse_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len);
  328. //
  329. // Numeric
  330. //
  331. // Returns 1 on sucess, 0 if value in array is too big
  332. char bit_array_as_num(const BIT_ARRAY* bitarr, uint64_t* result);
  333. // 1 iff bitarr > value
  334. // 0 iff bitarr == value
  335. // -1 iff bitarr < value
  336. int bit_array_cmp_uint64(const BIT_ARRAY* bitarr, uint64_t value);
  337. //
  338. // Arithmetic
  339. //
  340. // bitarr will be extended if needed
  341. void bit_array_add_uint64(BIT_ARRAY* bitarr, uint64_t value);
  342. // Add `add` to `bitarr` at `pos` -- same as:
  343. // bitarr + (add << pos)
  344. // where pos can be bigger than the length of the array (bitarr will be resized)
  345. void bit_array_add_word(BIT_ARRAY *bitarr, bit_index_t pos, uint64_t add);
  346. // Add `add` to `bitarr` at `pos`
  347. void bit_array_add_words(BIT_ARRAY *bitarr, bit_index_t pos, const BIT_ARRAY *add);
  348. // If value is greater than bitarr, bitarr is not changed and 0 is returned
  349. // Returns 1 on success, 0 if value > bitarr
  350. char bit_array_sub_uint64(BIT_ARRAY* bitarr, uint64_t value);
  351. // minus `minus` from `bitarr` at `pos` -- same as:
  352. // bitarr + (minus << pos)
  353. // Returns 1 on success, 0 if value > bitarr
  354. char bit_array_sub_word(BIT_ARRAY *bitarr, bit_index_t pos, word_t minus);
  355. // minus `minus` from `bitarr` at `pos`
  356. // Returns 1 on success, 0 if value > bitarr
  357. char bit_array_sub_words(BIT_ARRAY* bitarr, bit_index_t pos, BIT_ARRAY* minus);
  358. // Multiply by some value
  359. void bit_array_mul_uint64(BIT_ARRAY *bitarr, uint64_t multiplier);
  360. // bitarr = round_down(bitarr / divisor)
  361. // rem = bitarr % divisor
  362. void bit_array_div_uint64(BIT_ARRAY *bitarr, uint64_t divisor, uint64_t *rem);
  363. //
  364. // Arithmetic between arrays
  365. //
  366. // dst = src1 + src2
  367. // src1, src2 and dst can all be the same BIT_ARRAY
  368. // If dst is shorter than either of src1, src2, it is enlarged
  369. void bit_array_add(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2);
  370. // dst = src1 - src2
  371. // src1, src2 and dst can all be the same BIT_ARRAY
  372. // If dst is shorter than src1, it will be extended to be as long as src1
  373. // src1 must be greater than or equal to src2 (src1 >= src2)
  374. void bit_array_subtract(BIT_ARRAY* dst,
  375. const BIT_ARRAY* src1, const BIT_ARRAY* src2);
  376. // dst = src1 * src2
  377. // Pointers cannot all point to the same BIT_ARRAY
  378. void bit_array_multiply(BIT_ARRAY *dst, BIT_ARRAY *src1, BIT_ARRAY *src2);
  379. // Results in:
  380. // quotient = dividend / divisor
  381. // dividend = dividend % divisor
  382. // (dividend is used to return the remainder)
  383. void bit_array_divide(BIT_ARRAY *dividend, BIT_ARRAY *quotient, BIT_ARRAY *divisor);
  384. //
  385. // Read/Write bit_array to a file
  386. //
  387. // File format is [8 bytes: for number of elements in array][data]
  388. // Number of bytes of data is: (int)((num_of_bits + 7) / 8)
  389. //
  390. // Saves bit array to a file
  391. // returns the number of bytes written
  392. bit_index_t bit_array_save(const BIT_ARRAY* bitarr, FILE* f);
  393. // Reads bit array from a file. bitarr is resized and filled.
  394. // Returns 1 on success, 0 on failure
  395. char bit_array_load(BIT_ARRAY* bitarr, FILE* f);
  396. //
  397. // Hash function
  398. //
  399. // Pass seed as 0 on first call, pass previous hash value if rehashing due
  400. // to a collision
  401. // Using bob jenkins hash lookup3
  402. uint64_t bit_array_hash(const BIT_ARRAY* bitarr, uint64_t seed);
  403. //
  404. // Randomness
  405. //
  406. // Set bits randomly with probability prob : 0 <= prob <= 1
  407. void bit_array_random(BIT_ARRAY* bitarr, float prob);
  408. // Shuffle the bits in an array randomly
  409. void bit_array_shuffle(BIT_ARRAY* bitarr);
  410. // Get the next permutation of an array with a fixed size and given number of
  411. // bits set. Also known as next lexicographic permutation.
  412. // Given a bit array find the next lexicographic orginisation of the bits
  413. // Number of possible combinations given by (size choose bits_set) i.e. nCk
  414. // 00011 -> 00101 -> 00110 -> 01001 -> 01010 ->
  415. // 01100 -> 10001 -> 10010 -> 10100 -> 11000 -> 00011 (back to start)
  416. void bit_array_next_permutation(BIT_ARRAY* bitarr);
  417. //
  418. // Generally useful functions
  419. //
  420. // Generalised 'binary to string' function
  421. // Adds bits to the string in order of lsb to msb
  422. // e.g. 0b11010 (26 in decimal) would come out as "01011"
  423. char* bit_array_word2str(const void *ptr, size_t num_of_bits, char *str);
  424. // Same as above but in reverse
  425. char* bit_array_word2str_rev(const void *ptr, size_t num_of_bits, char *str);
  426. #ifdef __cplusplus
  427. }
  428. #endif
  429. #endif