How to implement a bitmap optimally in memory?

Question

Algorithms

Please tell me how to implement the bit matrix as efficiently as possible from memory so that the bits are stored as compactly as possible, but at the same time it would be possible to safely multiply the matrix by the matrix, as well as add the rows and columns in the matrix.

Answer 1

As compact as possible - store a one-dimensional matrix in bits of an integer array - 8 bits per byte.
For an NxM matrix, bits (i,j) will lie in the (i*N+j)/8 cell of the array. Bit number - you need to take the remainder of the division by 8.
You can get any bit and you can do anything with the matrix.

Answer 2

If the matrix is ​​sparse (a lot of zeros), then it is better to store it in a compressed form , the choice of algorithm depends on the degree of sparseness
, the storage method, different from just an array of bytes, is actually determined by the indexes that you will build to speed up and store compressed data,
for example, you can store a vector in the form of three lists key-value dictionaries, one - a list of bytes with mixed bit values, a list with only zeros or a list with only ones (it is enough to store only one of these two, the absence of values ​​in the first and second lists will show that the element is in the third)
the matrix can be stored both row by row and squares (for example, 8x8 bit submatrices), the choice of how the matrix is ​​divided into blocks will determine the nature of the distribution of elements (in the above example, this makes sense if the bits have the property 'stick to each other', i.e. the probability that the bit will be set next to another set higher than among empty bits)