[x] My submission is formatted according to the guidelines in the contributing guide
[ ] My addition is on refer on the language README.md file
[ ] My addition does not have a spelling problem
[ ] My submission has a proper and user-friendly description of the algorithm
[ ] My submission has the time complexity of the algorithm
[x] My submission has sample input-output of the program (NOT FOR PYTHON)
What kind of change does this PR introduce? (check at least one)
[ ] Bugfix
[ ] New algorithm
[ ] Optimization in previous algorithms
[ ] Code style update
[ ] Refactor
[ ] Documentation
[x] Other, please describe: I have added a data structure Bit-Array, with its respective operations.
Briefly describe the changes in this PR
BitArray Structure
Structure Definition: The BitArray struct consists of an unsigned int* array pointer to store the actual bits and a size_t size to keep track of the number of bits.
Why unsigned int: unsigned int is used for the storage array to ensure that the storage is treated as a sequence of bits without a sign bit. This choice maximizes portability and efficiency for bitwise operations.
Key Functions and Operations
Creating and Freeing Bit Arrays:
createBitArray(size_t n): Allocates memory for a new bit array of n bits, initializing all bits to 0.
freeBitArray(BitArrayPtr bit_array): Frees the allocated memory for a bit array to prevent memory leaks.
Basic Bit Manipulations:
setBit(BitArray* ba, size_t index): Sets a bit to 1 at the specified index.
clearBit(BitArray* ba, size_t index): Clears a bit (sets to 0) at the specified index.
toggleBit(BitArray* ba, size_t index): Toggles a bit at the specified index.
testBit(const BitArray* ba, size_t index): Tests whether a bit at the specified index is set or not.
Advanced Operations:
findFirstSetBit, findFirstUnsetBit: Searches for the first set (1) or unset (0) bit in the array.
hammingWeightBitArray: Calculates the Hamming weight (number of set bits).
Bitwise operations like AND, OR, NOT, XOR, shifts, and rotates, allowing for complex manipulation of bit sets.
Utility and Convenience:
printBitArray: Prints the bit array for debugging and visualization.
Operations like bitwiseShiftLeft, bitwiseShiftRight, bitwiseRotateLeft, and bitwiseRotateRight provide ways to shift or rotate bits within the array, which can be useful for algorithms that require bit manipulation, such as cryptography or compression algorithms.
bitSlice, unionBitArrays, intersectionBitArrays, differenceBitArrays, resizeBitArray: These functions provide additional operations like slicing a bit array, performing set operations (union, intersection, difference), and resizing a bit array.
Other information:
Use Cases and Applications
Bit arrays are widely used in situations where memory efficiency is crucial, and operations can be represented as sets of binary states. Common applications include:
Efficient Storage: Storing compact flags or states for a large number of entities.
Set Operations: Performing quick set operations like unions, intersections, and differences.
Algorithm Optimization: In algorithms that benefit from bit-level operations, such as cryptographic algorithms, compression techniques, and more.
Data Structures: Implementing other data structures like Bloom filters or bitmaps used in databases and indexing.
PR Checklist:
What kind of change does this PR introduce? (check at least one)
Briefly describe the changes in this PR
BitArray Structure
BitArray
struct consists of anunsigned int* array
pointer to store the actual bits and asize_t size
to keep track of the number of bits.unsigned int
:unsigned int
is used for the storage array to ensure that the storage is treated as a sequence of bits without a sign bit. This choice maximizes portability and efficiency for bitwise operations.Key Functions and Operations
Creating and Freeing Bit Arrays:
createBitArray(size_t n)
: Allocates memory for a new bit array ofn
bits, initializing all bits to 0.freeBitArray(BitArrayPtr bit_array)
: Frees the allocated memory for a bit array to prevent memory leaks.Basic Bit Manipulations:
setBit(BitArray* ba, size_t index)
: Sets a bit to 1 at the specified index.clearBit(BitArray* ba, size_t index)
: Clears a bit (sets to 0) at the specified index.toggleBit(BitArray* ba, size_t index)
: Toggles a bit at the specified index.testBit(const BitArray* ba, size_t index)
: Tests whether a bit at the specified index is set or not.Advanced Operations:
findFirstSetBit
,findFirstUnsetBit
: Searches for the first set (1) or unset (0) bit in the array.hammingWeightBitArray
: Calculates the Hamming weight (number of set bits).Utility and Convenience:
printBitArray
: Prints the bit array for debugging and visualization.bitwiseShiftLeft
,bitwiseShiftRight
,bitwiseRotateLeft
, andbitwiseRotateRight
provide ways to shift or rotate bits within the array, which can be useful for algorithms that require bit manipulation, such as cryptography or compression algorithms.bitSlice
,unionBitArrays
,intersectionBitArrays
,differenceBitArrays
,resizeBitArray
: These functions provide additional operations like slicing a bit array, performing set operations (union, intersection, difference), and resizing a bit array.Other information:
Use Cases and Applications
Bit arrays are widely used in situations where memory efficiency is crucial, and operations can be represented as sets of binary states. Common applications include: