Generate all bit patterns for a given mask

Question

My problem is as follows: I have a value x and a pattern p both variables of the same size. The goal is to iterate through all bit patterns of x that are not masked by p.

Example: if we have p = 1001, we want to find 0000, 0001, 1000, and 1001 - not necessarily in that order.

Standard implementation in C99 (the return value specifies whether we have returned all values already):

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == mask) {
        return false;
    }
    size_t current = val & mask;
    size_t inc = 1;
    size_t new_val = current + inc;
    while ((new_val & mask) <= current) {
        inc++;
        new_val = current + inc;
    }
    *out = new_val;
    return true;
}

I would think there should be some trick to make this more efficient, but I can't seem to find any big improvements (apart from computing the trailing zeros of the mask and setting the start value of inc appropriately, which isn't much of an improvement).

Edit: Also important is the fact that for each generated value lots of additional work is generated, which means that lots of duplicates are out of the question (some duplicates, even if not recognizable would be ok, there aren't any side effects to the work done, it's just a slowdown).

Answer 1

This generates all bit patterns in reverse order (initial value of val should be equal to mask):

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == 0) {
        return false;
    }

    *out = (val - 1) & mask;
    return true;
}

---

And this (slightly less obvious code) generates all bit patterns in direct order (initial value of val should be zero):

static bool next(size_t val, size_t mask, size_t *out) {
    if (val == mask) {
        return false;
    }

    *out = (val - mask) & mask;
    return true;
}

Answer 2

From your example, it looks like this pseudo-code will do the trick:

current = p // set up current
getNotMasked(p, 0) // initial call


bitString current

getNotMasked(int pos)
  if (pos == current.length)
    print(current)
    return
  if (current[pos] == 1)
    current[pos] = 0
    getNotMasked(pos+1)
    current[pos] = 1
    getNotMasked(pos+1)
  else
    getNotMasked(pos+1)

Generating C code from here shouldn't be difficult - replace bitString with int and [pos] with & 1 << pos or similar.