Packing Small Integers into Bit Fields

Several small unsigned integers can share one machine word when each value has a known upper bound. The technique is useful for binary protocols, hardware registers, compact state tables, and memory-sensitive data structures. It is usually called bit-field packing: each value owns a fixed range of bits inside a larger unsigned integer.

Packing is not automatically an optimization. A database may store or index ordinary columns more effectively, and a packed layout is harder to query and evolve. The method is most useful when the binary representation itself is part of the design rather than merely a way to avoid a few bytes.

How Many Bits Does a Value Need?

A field of width k represents the unsigned values from zero through 2^k - 1. If the largest required value is maximum, the minimum width is

Values no larger than 10 therefore need four bits because \(2^3-1=7<10\le 15=2^4-1\). A 32-bit word can hold eight independent four-bit values. This calculation must include every valid future value; widening a field later changes the position of every field above it.

Extracting a Field

Let word contain a field that begins at bit offset, counting the least significant bit as position zero, and let the field occupy width bits. A mask of width low one-bits is

Shifting right moves the field to bit zero. AND with \(M\) then discards every bit that was originally above the field:

This is the same bit-mask construction used for ordinary set, clear, and toggle operations, applied to several adjacent bits at once.

Replacing a Field Without Touching Its Neighbors

Writing a field takes two independent operations. First move the low-bit mask into place, \(F=M\ll\text{offset}\), and clear that range with word & ~F. Then restrict the new value to the field width, shift it into place, and combine the two parts with OR:

Masking value before shifting is essential. Without value & M, a value that needs more than width bits spills into the neighboring field even though the destination range was cleared correctly.

A Safe 32-Bit C Implementation

Unsigned fixed-width types give these operations explicit modulo-\(2^{32}\) semantics. The full width needs one special case because shifting a 32-bit value by 32 positions is undefined in C.

#include <assert.h>
#include <stdint.h>

static uint32_t low_mask(unsigned width) {
  assert(width > 0 && width <= 32);
  return width == 32
    ? UINT32_MAX
    : (UINT32_C(1) << width) - UINT32_C(1);
}

uint32_t extract_field(uint32_t word, unsigned offset, unsigned width) {
  assert(offset < 32 && width > 0 && width <= 32 - offset);
  return (word >> offset) & low_mask(width);
}

uint32_t replace_field(
  uint32_t word,
  unsigned offset,
  unsigned width,
  uint32_t value
) {
  assert(offset < 32 && width > 0 && width <= 32 - offset);

  uint32_t value_mask = low_mask(width);
  uint32_t field_mask = value_mask << offset;

  return (word & ~field_mask) | ((value & value_mask) << offset);
}

The preconditions make offset + width stay inside the word. Production APIs can return an error instead of asserting, but silently accepting an invalid layout is dangerous: C does not define an out-of-range shift as a harmless zero.

Worked Example

Consider the unsigned value 4283942, whose hexadecimal representation is 0x415E26. Bits 4 through 8 form a five-bit field, so its offset is 4, its width is 5, and its mask is 0x1F:

extract_field(4283942, 4, 5) == 2

Replacing that field with decimal 10 changes only those five bits:

replace_field(4283942, 4, 5, 10) == 4284070
extract_field(4284070, 4, 5) == 10

In binary, the local change is easy to see. The surrounding bits remain identical:

before: 0100 0001 0101 1110 0010 0110
after:  0100 0001 0101 1110 1010 0110

Building a Fixed Layout

A packed format should name every field and keep its offset and width in one place. For example, eight four-bit values can occupy one uint32_t, with slot zero in the lowest nibble:

uint32_t set_slot(uint32_t word, unsigned slot, uint32_t value) {
  assert(slot < 8);
  return replace_field(word, slot * 4, 4, value);
}

uint32_t get_slot(uint32_t word, unsigned slot) {
  assert(slot < 8);
  return extract_field(word, slot * 4, 4);
}

Centralizing the layout avoids scattering unexplained shifts throughout a program. It also makes overlap checks, versioning, and serialization tests possible. Bit zero is always the least significant bit of the integer; byte order becomes relevant only when that integer is written to or read from a byte stream.

When Packing Is the Wrong Tradeoff

• Independent queries: database columns are usually easier to index and filter than fields hidden inside one integer.
• Frequent schema changes: increasing one field's width can require a new layout and a data migration.
• Concurrent updates: two writers changing different fields still modify the same containing word and can overwrite one another without an atomic read-modify-write operation.
• Signed values: a signed field needs an explicit representation and sign-extension rule; the helpers above intentionally handle only unsigned fields.
• Untrusted input: decide whether an oversized value should be rejected or truncated. The implementation above truncates it with a mask.

Bit-field packing is strongest when the format is fixed, compactness matters, and all access goes through tested helpers. When readability, independent indexing, or schema flexibility matters more, ordinary fields are generally the better representation.