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.

  • 7
    In C#, there are enums, and they can have a Flags attribute. They could make your code far simpler. – Bernhard Hiller Oct 15 at 8:58
  • 10
    I'd call this "simulating bit fields". It is almost always a bad idea unless space efficiency is overwhelmingly important. – Kilian Foth Oct 15 at 9:17
  • 5
    @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. – cmaster Oct 15 at 14:19
  • 3
    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. – JimmyJames Oct 15 at 16:22
  • 3
    @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. – Bill K Oct 15 at 20:33
up vote 105 down vote accepted

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.

  • 4
    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. – Peter Green Oct 15 at 17:25
  • 20
    @PeterGreen That would be different than the standard interpretation. – Eric Oct 15 at 19:26
  • 1
    "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). – mckenzm Oct 16 at 3:50
  • 1
    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). – Luaan Oct 16 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. – Glorfindel Oct 16 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. – Greg Burghardt Oct 15 at 16:16
  • 12
    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 chars into one int. – Izkata Oct 15 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/… – Bill K Oct 15 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. – Dan Neely Oct 15 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. – Luaan Oct 16 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.
(i.e. using a bit mask.)


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);
}
  • 1
    this.stateF = (num & 32) ? true : false, etc. No need to mutate num while you're extracting the values. – Roger Lipscombe Oct 16 at 11:09
  • 3
    @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. – Pharap Oct 16 at 11:31

protected by gnat Oct 16 at 8:44

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.