Binary Encoding

September 2026 · 10 min read

Binary encoding assigns each category an integer ID, writes that ID in base two, and gives the model one column per bit. It can distinguish many category names with fewer columns than a full one-hot representation.

For seven names A through G, use IDs 1 through 7 and reserve ID 0 for unknown names. Three bits are enough: C has ID 3, written 011. The model receives three separate values, [0, 1, 1].

Read a code as a pattern of bits

From left to right, our bit positions represent 4, 2, and 1. C’s pattern means 0 × 4 + 1 × 2 + 1 × 1 = 3. Those place values reconstruct the ID; they are not model coefficients. Click a category to follow the conversion.

How many columns do we save?

With $d$ binary columns, there are $2^d$ possible patterns. For $K$ known categories plus one reserved unknown pattern, choose the smallest $d$ with enough patterns:

The ceiling means round up to the next integer. Seven known categories and one unknown pattern need three columns. Eight known categories need four under this convention. For 1,000 known categories, ten columns suffice instead of 1,000 full one-hot columns.

The extra pattern is a policy choice. If every bit pattern were assigned to a known name, a different mechanism would be needed for unknowns. Libraries can use additional missing or unknown indicators, so inspect the fitted output columns rather than assuming this formula covers every configuration.

Compact codes introduce a geometry

The original names A, B, C, and D have no stated similarity. Their codes nevertheless have different distances. For zero-or-one vectors, the squared Euclidean distance equals the number of differing bits:

Changing the category-to-ID assignment changes these relationships. Distance-based models may react to them. Full one-hot vectors instead put distinct categories at the same distance within a feature block.

Binary encoding also differs from feeding the integer itself into one numerical column. Bit columns do not force effects to follow the numeric ID’s order. They introduce their own pattern of sharing.

Fewer columns change what the model can express

A linear model gives one coefficient to each bit. For seven categories, three bit coefficients and an intercept provide only four adjustable numbers. They cannot represent seven arbitrary independent category effects.

A decision tree can test several bits to identify a category. One bit test usually groups several names, so the required splits differ from one-hot tests. Compare the complete encoding-and-model combination rather than treating bit conversion as a neutral storage trick.

Save the mapping, width, and bit order

The encoder must use the same ID for each name at prediction time. Fit the vocabulary on training data, or supply a domain vocabulary fixed independently of the held-out data. Save the category map, number of bits, left-to-right bit order, and unknown policy alongside the model.

Our all-zero fallback distinguishes unknown inputs from every known pattern, but the model does not learn an unknown effect if that pattern never appeared in training. It also merges all unseen names. Treat missing inputs separately when needed; these examples assume non-missing strings.

class BinaryMap:
    def __init__(self, vocabulary):
        if not vocabulary or len(set(vocabulary)) != len(vocabulary):
            raise ValueError("use a nonempty vocabulary with unique names")
        self.codes = {name: i + 1 for i, name in enumerate(vocabulary)}
        self.width = len(vocabulary).bit_length()

    def transform(self, values):
        result = []
        for name in values:
            code = self.codes.get(name, 0)  # Reserved all-zero unknown code.
            result.append([(code >> shift) & 1
                           for shift in range(self.width - 1, -1, -1)])
        return result

encoder = BinaryMap(["A", "B", "C", "D", "E", "F", "G"])
print(encoder.transform(["A", "C", "D", "new"]))
assert encoder.transform(["A", "C", "D", "new"]) == [
    [0, 0, 1], [0, 1, 1], [1, 0, 0], [0, 0, 0]
]

[[0, 0, 1], [0, 1, 1], [1, 0, 0], [0, 0, 0]]

Do not append a new category to this map while serving an existing model. It may change the required width, and even when spare patterns exist, the model has not learned the new category’s effect. Retraining creates a new encoder-and-model version.

Choose it for a measured width tradeoff

Binary codes reduce the output width, but the encoder still stores one mapping entry per category. Hashing avoids a learned vocabulary at the cost of collisions. Our binary mapping is collision-free among known categories; its modeling constraints come from sharing bit columns.

One-hot input can also be stored sparsely, while a binary row may contain several ones. Fewer columns do not automatically mean a smaller sparse input matrix or better predictions. Measure memory and validation performance, including behavior on rare and unseen names.

Keep the vocabulary construction inside each training fold. If category order is chosen using target statistics, that is an additional supervised step with its own leakage boundary; the simple code here uses only a supplied list of names.

C++: convert a saved ID into separate bits

The constructor reserves zero and rejects empty or duplicate vocabularies. Each lookup returns bits from the most significant position to the least significant one. It never adds an unseen name to the map.

#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

class BinaryMap {
    std::unordered_map<std::string, std::size_t> codes;
    std::size_t width = 0;
public:
    explicit BinaryMap(const std::vector<std::string>& vocabulary) {
        if (vocabulary.empty()) throw std::invalid_argument("empty vocabulary");
        for (std::size_t i = 0; i < vocabulary.size(); ++i)
            if (!codes.emplace(vocabulary[i], i + 1).second)
                throw std::invalid_argument("duplicate category");
        for (std::size_t n = vocabulary.size(); n; n >>= 1) ++width;
    }
    std::vector<int> encode(const std::string& name) const {
        const auto found = codes.find(name);
        const std::size_t code = found == codes.end() ? 0 : found->second;
        std::vector<int> bits(width);
        for (std::size_t i = 0; i < width; ++i)
            bits[i] = static_cast<int>((code >> (width - 1 - i)) & 1);
        return bits;
    }
};

int main() {
    const BinaryMap encoder({"A", "B", "C", "D", "E", "F", "G"});
    for (const std::string name : {"A", "C", "D", "new"}) {
        std::cout << name << ":";
        for (int bit : encoder.encode(name)) std::cout << " " << bit;
        std::cout << "\n";
    }
}

A: 0 0 1
C: 0 1 1
D: 1 0 0
new: 0 0 0

References and further reading

• Category Encoders: BinaryEncoder — the library’s bit-column representation and configurable missing/unknown behavior.
• Category Encoders: BaseNEncoder source — digit-width calculation, integer-to-base conversion, and fitted mappings.
• Python: int.bit_length — the integer bit-width operation used in the teaching implementation.