Read/Write compressed binary data.

Question

I read all over the place people talk about compressing objects on a bit by bit scale. Things like "The first three bits represent such and such, then the next two represent this and twelve bits for that"

I understand why it would be desirable to minimize memory usage, but I cannot think of a good way to implement this. I know I would pack it into one or more integers (or longs, whatever), but I cannot envision an easy way to work with it. It would be pretty cool if there were a class where I could get/set arbitrary bits from an arbitrary length binary field, and it would take care of things for me, and I wouldn't have to go mucking about with &'s and |'s and masks and such.

Is there a standard pattern for this kind of thing?

Answer 1

From MSDN:

BitArray Class

Manages a compact array of bit values, which are represented as Booleans, where true indicates that the bit is on (1) and false indicates the bit is off (0).

Example:

BitArray myBitArray = new BitArray(5);
myBitArray[3] = true; // set bit at offset 3 to 1

BitArray allows you to set only individual bits, though. If you want to encode values with more bits, there's probably no way around mucking about with &'s and |'s and masks and stuff :-)

Answer 2

What you're looking for are called bitwise operations.

For example, let's say we're going to represent an RGB value in the least significant 24 bits of an integer, with R being bits 23-16, G being bits 15-8, and B being bits 7-0.

You can set R to any value between 0 and 255 without effecting the other bits like this:

void setR(ref int RGBValue, int newR)
{
  int newRValue = newR << 16; // shift it left 16 bits so that the 8 low-bits are now in position 23-16
  RGBValue = RGBValue & 0x00FF; // AND it with 0x00FF so that the top 16 bits are set to zero
  RGBValue = RGBValue | newRValue;   // now OR it with the newR value so that the new value is set.
}

By using bitwise ANDs and ORs (and occasionally more exotic operations) you can easily set and clear any individual bit of a larger value.

Answer 3

Rather than using toolkit or platform specific wrapper classes I think you are better off biting the bullet and learning your &s and |s and 0x04s and how all the bitwise operators work. By and large that's how its done for most projects, and the operations are extremely fast. The operations are pretty much identical on most languages so you won't be stuck dependant on some specific toolkit.

Answer 4

You might want to check out the BitVector32 structure in the .NET Framework. It lets you define "sections" which are ranges of bits within an int, then read and write values to those sections.

The main limitation is that it's limited to a single 32-bit integer; this may or may not be a problem depending on what you're trying to do. As dtb mentioned, BitArray can handle bit fields of any size, but you can only get and set a single bit at a time--there is no support for sections as in BitVector32.