# What is the name for storing / packing many boolean states into one number?

It's a sort of simple compression where you use one numeric variable to store many boolean / binary states, using doubling and the fact that every doubling number is 1 + the sum of all the previous ones.

I'm sure it must be an old, well-known technique, I'd like to know what it's called to refer to it properly. I've done several searches on every way I can think of to describe it, but found nothing beyond some blog articles where the article authors seem to have figured this out themselves and don't know what to call it, either (example 1, example 2).

For example, here's a very simple implementation intended to illustrate the concept:

``````packStatesIntoNumber () {
let num = 0
if (this.stateA) num += 1
if (this.stateB) num += 2
if (this.stateC) num += 4
if (this.stateD) num += 8
if (this.stateE) num += 16
if (this.stateF) num += 32
return num
}

unpackStatesFromNumber (num) {
assert(num < 64)
this.stateF = num >= 32; if (this.stateF) num -= 32
this.stateE = num >= 16; if (this.stateE) num -= 16
this.stateD = num >= 8; if (this.stateD) num -= 8
this.stateC = num >= 4; if (this.stateC) num -= 4
this.stateB = num >= 2; if (this.stateB) num -= 2
this.stateA = num >= 1; if (this.stateA) num -= 1
}
``````

You could also use bitwise operators, base 2 number parsing, enums... There are many more efficient ways to implement it, I'm interested in the name of the approach more generally.

• In C#, there are `enums`, and they can have a `Flags` attribute. They could make your code far simpler. Oct 15 '18 at 8:58
• I'd call this "simulating bit fields". It is almost always a bad idea unless space efficiency is overwhelmingly important. Oct 15 '18 at 9:17
• @KilianFoth A `bool` is generally stored as a 32 bit integer internally. As such, packing can make the difference of a factor of 32. That's really a lot. I mean, we programmers are always ready to throw away half of our resources, but I'm generally reluctant to throw away 97% of them. Such waste factors can easily make the difference between being able to run important use cases and running out of memory. Oct 15 '18 at 14:19
• Historically, the typically way bit masks are used to declare, set and retrieve values. Using shifts is odd and not really the best illustration of the approach. Oct 15 '18 at 16:22
• @cmaster The reason bools are stored that way is because sharing a single memory location (32 or 64 bits on todays machines) can be very bad for cache performance unless you pay a lot of attention to the machine language code. If you have a truly massive number of bits it's probably worth it, but if not you are probably better off not pre-optimizing and just packing the bits up when you are ready to transmit to network or disk. Oct 15 '18 at 20:33

It's most commonly referred to as a bit field, and another term you'll often hear is bit masks, which are used to get or set individual bit values or the entire bit field at once.

Many programming languages have auxiliary structures to help with this. As @BernhardHiller notes in the comments, C# has enums with flags; Java has the EnumSet class.

• I would interpret "bit field" as using a language feature that allows individual bits to be assigned to fields of a structure rather than doing it manually with bitwise operators. Oct 15 '18 at 17:25
• @PeterGreen That would be different than the standard interpretation.
– Eric
Oct 15 '18 at 19:26
• "Bit Mapping" or "Bit Mapped" , whilst common for recordsets and array processing, can also apply in this case. When extracting common elements from multiple sets the value can be decomposed to identify components of a federated model. We even say this of octal filemode digits. Bit Masks (any mask) tend to be filters (as for IO ports and data direction registers). Oct 16 '18 at 3:50
• C# also has `BitArray`, which allows storing an arbitrary amount of bits and indexing them (while flags are limited to an integer type and intended to be used as masks). Oct 16 '18 at 6:31
• True; I just mentioned the two structures I'm most familiar with. There are probably dozens out there, especially in other languages. Oct 16 '18 at 6:43

Strange, quite a bit of different terms here but I don't see the one that came immediately to mind (and it's in the title of your question!)--Bit Packing is what I've always heard it termed.

I had thought this was really obvious but strangely when I google it this seems to be a term that is widely used but not officially defined (Wikipedia seems to redirect to bit field which is a way to do bit packing, but not a name for the process). Searching for the definition seems to lead to this page:

http://www.kinematicsoup.com/news/2016/9/6/data-compression-bit-packing-101

Which isn't great for SO purposes but it's the best definition/description I can find including this succinct description: "Bit-packing is a simple concept: Use as few bit as possible to store a piece of data."

• Can you provide some references? Interesting term. Oct 15 '18 at 16:16
• Bit packing is technically correct but also refers to a more general a thing than just boolean states - storing data in general in the smallest number of bits as possible. For example, another use of it could mean compressing a `char` array by putting two `char`s into one `int`. Oct 15 '18 at 16:22
• @GregBurghardt You know, it's interesting. I didn't think about it when I posted because the term was so prevalent in the 80's/90's when I learned programming in C and assembly--now although a google search finds MANY mentions, there isn't a definitive Wikipedia page for it. The first answer in google has this definition: "Bit-packing is a simple concept: Use as few bit as possible to store a piece of data." kinematicsoup.com/news/2016/9/6/… Oct 15 '18 at 16:39
• that's when I learned about bit packing too, although you can get a lot crazier than simply repurposing unused 0's in what would nominally be integer values. some years back I ran into a system that stored one of its parameters as an 8 bit float. IIRC 5 bits for an unsigned mantissa (all values were positive no need to store the sign explicitly), and 3 more for a base 10 exponent. At the time I'd assumed it was a legacy hardware kludge with no path forward, but with machine learning having recently started doing stuff with int4 vs int8, I could see some workloads dropping down from FP16. Oct 15 '18 at 18:06
• @DanNeely This kind of thing is also commonly supported by GPUs - trading between precision, memory and computation is pretty important there. This has been exploited pretty well with GPU-based computing too. Oct 16 '18 at 6:32

There are many different terms used to describe this.

Most commonly the bits are called "bit flags" or "bit fields".
(However, it's worth noting that "bit fields" sometimes refers to a specific feature of the C and C++ languages, which is related but not exactly the same.)

The integer itself is referred to variously as either a "bit array", a "bit set" or a "bit vector", depending on usages and circumstances.

Either way, extracting the bits from the bit set/vector/array is done through shifting and masking.

For some examples of each term in active use:

It's not really pertinent to the question but I'd like to say: please do not use addition and subtraction to set and clear bits as those methods are prone to error.
(i.e. if you do `num += 1` twice, the result is equivalent to `num += 2`.)

Prefer to use the appropriate bitwise operations instead, if your chosen language provides them:

``````packStatesIntoNumber ()
{
let num = 0
if (this.stateA) num |= 1
if (this.stateB) num |= 2
if (this.stateC) num |= 4
if (this.stateD) num |= 8
if (this.stateE) num |= 16
if (this.stateF) num |= 32
return num
}

unpackStatesFromNumber (num)
{
this.stateF = ((num & 32) != 0);
this.stateE = ((num & 16) != 0);
this.stateD = ((num & 8) != 0);
this.stateC = ((num & 4) != 0);
this.stateB = ((num & 2) != 0);
this.stateA = ((num & 1) != 0);
}
``````
• `this.stateF = (num & 32) ? true : false`, etc. No need to mutate `num` while you're extracting the values. Oct 16 '18 at 11:09
• @RogerLipscombe Good point, I wasn't really reading through what the code was doing, just reacting to the use of `+` and `-`. I've now gone one better and used `!= 0` instead of a ternary, which I feel is more concise whilst still being expclit. Oct 16 '18 at 11:31