---
title: "A little XOR trick to micro-optimize some integer data structures"
date: 2025-08-13
taxonomies:
  tags: ["programming", "c"]
---

Motivating example
==================

Say you want to write an integer hash-set implementation in C. You might start like this:

    /* a hash-set implemented with a flat open-addressed array with linear probing */
    struct set {
        int *entries;
        size_t N;
    };

    void set_init(struct set *set, size_t initial) {
        /* make sure N is a power of 2, with enough capacity to minimize collisions */
        for (set->N = 8; set->N < initial * 2; set->N *= 2) ;
        set->entries = calloc(set->N, sizeof *set->entries);
    }

    unsigned inthash(unsigned x) { ... }

    bool set_contains(struct set *set, int x) {
        int h = inthash(x) & (set->N - 1), i = h;
        do {
     ---->  if (entry i is empty)  <----
                return 0;
            else if (set->entries[i] == x)
                return 1; 
            i = (i + 1) & (set->N - 1);
        } while (i != h);
        /* set is full, looped around */
        return 0;
    }

    void _set_grow(struct set *set) { ... } // omitted for brevity

    void set_put(struct set *set, int x) {
        int h = inthash(x) & (set->N - 1), i = h;
        do {
     ---->  if (entry i is empty)  <----
                set->entries[i] = x;
            else if (set->entries[i] == x)
                return; /* nothing to do */
            i = (i + 1) & (set->N - 1);
        } while (i != h);
        /* full set, looped around */
        _set_grow(set);
        set_put(set, x);
    }

The problem is, if every array item can hold a key, how do you mark an entry as
empty?  There's two ways you can go about this:
  - Out-of-band signaling, so you keep a separate array `bool *hasentry` also of size N,
    which for every index stores whether the corresponding entry is used or
    empty. Initialized to zeroes and updated when new entries are added in
    `set_put`.  Instead of 1 byte per entry with a bool array, you can be more
    efficient using a bit array.  This is the generalized approach that is useful
    if the values the set is storing are truly arbitrary.
  - In-band signaling, meaning you reserve a special sentinel value to
    represent an empty entry. This places a restriction in the values your set can hold,
    but very often this is fine. This technique is for this use case.

So the easy case is if your sentinel value is zero, then it's a matter of changing

           if (entry i is empty)       

into

           if (!set->entries[i])

and adding a check like

    void set_put(struct set *set, int x) {
        assert(x != 0 && "illegal value");
        ...
    }

Note that in `set_init` (and `_set_grow`), the use of `calloc` already zeroes
the whole array, marking it initially as all empty, exactly as we want.

But in practice, very often the integers you might wanna store in the set are
not arbitrary (so you can use the sentinel technique), but zero is a value you
would like to be able to store, thus not a good sentinel. In this case you have
to fallback to a non-zero sentinel, for example

    #define _SET_EMPTY INT_MIN

    void set_init(struct set *set, size_t initial) {
        ...
        set->entries = malloc(set->N);
        for (int i = 0; i < set->N; ++i) set->entries[i] = _SET_EMPTY;
    }

    bool set_contains(struct set *set, int x) {
      ...
            if (set->entries[i] == _SET_EMPTY)
                return 0;
      ...
    }

    void _set_grow(struct set *set) {
        int *old_entries = set->entries;
        size_t old_N = set->N;
        set->entries = malloc(set->N *= 2);
        for (int i = 0; i < set->N; ++i) set->entries[i] = _SET_EMPTY;
        ...
    }

    void set_put(struct set *set, int x) {
        assert(x != _SET_EMPTY && "illegal value");
      ...
            if (set->entries[i] == _SET_EMPTY)
                set->entries[i] = x;
      ...
    }

This works fine, but we lose the nicety of `calloc`.

My trick combines the benefits of the zero-sentinel (initialization for free)
and an arbitrary sentinel by simply storing the value XORed with the sentinel.
  - We keep the `calloc`s for zero initialization
  - `if (entry i is empty)` becomes `if (!set->entries[i])`
  - We XOR the value with the sentinel before storing it and when getting it
    out of an entry:

Thus:

    bool set_contains(struct set *set, int x) {
        int h = inthash(x) & (set->N - 1), i = h;
        do {
            if (!set->entries[i])
                return 0;
            else if ((set->entries[i] ^ _SET_EMPTY) == x)  // <--------
                return 1; 
            i = (i + 1) & (set->N - 1);
        } while (i != h);
        /* set is full, looped around */
        return 0;
    }

    void set_put(struct set *set, int x) {
        int h = inthash(x) & (set->N - 1), i = h;
        assert(x != _SET_EMPTY && "illegal value");
        do {
            if (!set->entries[i])
                set->entries[i] = x ^ _SET_EMPTY;  // <--------
            else if ((set->entries[i] ^ _SET_EMPTY) == x) // <-------
                return; /* nothing to do */
            i = (i + 1) & (set->N - 1);
        } while (i != h);
        /* full set, looped around */
        _set_grow(set);
        set_put(set, x);
    }

This works because of the mathematical properties of bitwise XOR:
  - `x^y == 0` if and only if `x == y`,
  - If `x^y = z` then `z^y = x` and `x^z = y` (XOR is reversible)

In situations where `calloc` is more efficient than `malloc` + manual
initialization, this is a potentially more efficient solution, especially if
the size of your set is unpredictable and could grow multiple times.