How can I manage bits/binary in c++?

Question

What I need to do is open a text file with 0s and 1s to find patterns between the columns in the file.

So my first thought was to parse each column into a big array of bools, and then do the logic between the columns (now in arrays). Until I found that the size of bools is actually a byte not a bit, so i would be wasting 1/8 of memory, assigning each value to a bool.

Is it even relevant in a grid of 800x800 values? What would be the best way to handle this? I would appreciate a code snippet in case its a complicated answer

Answer 1

you can use std::vector<bool> which is a specialization of vector that uses a compact store for booleans....1 bit not 8 bits.

Answer 2

For that size grid your array of bools would be about 640KB. Depends how much memory you have if that will be a problem. It would probably be the simplest for the logic analysis code.

By grouping the bits and storing in an array of int you could drop the memory requirement to 80KB, but the logic code would be more complicated as you'd be always isolating the bits you wanted to check.

Answer 3

I think it was Knuth who said "premature optimization is the root of all evil." Let's find out a little bit more about the problem. Your array is 800**2 == 640,000 bytes, which is no big deal on anything more powerful than a digital watch.

While storing it as bytes may seem wasteful -- as you say, 7/8ths of the memory is redundant -- but on the other hand, most machines don't do bit operations as efficiently as bytes; by saving the memory, you might waste so much effort masking and testing that you would have been better off with the bytes model.

On the other hand, if what you want to do with it is look for larger patterns, you might want to use a bitwise representation because you can do things with 8 bits at a time.

The real point here is that there are several possibilities, but no one can tell you the "right" representation without knowing what the problem is.

Answer 4

You could use std::bitset or Boosts dynamic_bitset which provide different methods which will help you manage your bits.

They for example support constructors which create bitsets from other default types like int or char. You can also export the bitset into an ulong or into a string (which then could be turned into a bitset again etc)

I once asked about concatenating those, which wasn't performantly possible to do. But perhaps you could use the info in that question too.