Better bit tricks in base2

base2 is an expensive enough operation compared to the rest of the function, even if inlined and unrolled. Therefore, optimizing it is likely to optimize the whole thing. Actually, our isomsb function sets all the bits at the right of the msb then only keeps the leftmost set bit. We can tweak the function so that it keeps the two leftmost set bits instead and have a base2 function no slower than isomsb:

// Return the greatest power of 2 not higher than // x where x and the power of 2 are encoded in Gray // code auto base2(gray_code<Unsigned> x) -> gray_code<Unsigned> { for (std::size_t i = 1u ; i <= std::numeric_limits<Unsigned>::digits / 2u ; i <<= 1u) { x |= x >> i; } return x & ~(x >> 2u); } 

Reuse already computed information

We can see that base2(lhs) and base2(rhs) are computed every time operator+ is called, but base(rhs) is sometimes already known before a recursive call and we could avoid recomputing it. Therefore, we can add a third parameter to the function to transmit rhs_base to the recursive call and let operator+ be a simple wrapper:

template<typename Unsigned> auto add(gray_code<Unsigned> lhs, gray_code<Unsigned> rhs, gray_code<Unsigned> rhs_base) -> gray_code<Unsigned> { auto lhs_base = base2(lhs); if (lhs_base == rhs_base) { if (lhs == rhs) { return (lhs << 1u) ^ is_odd(lhs); } return (lhs_base << 1u) ^ ((lhs_base ^ lhs) + (lhs_base ^ rhs)); } if (lhs_base.value < rhs_base.value) { std::swap(lhs, rhs); std::swap(lhs_base, rhs_base); } if (lhs == lhs_base) { return lhs ^ rhs; } auto tmp = add(lhs ^ lhs_base, rhs, rhs_base); if (base2(tmp).value < lhs_base.value) { return lhs_base ^ tmp; } return (lhs_base << 1u) ^ (lhs_base ^ tmp); } template<typename Unsigned> auto operator+(gray_code<Unsigned> lhs, gray_code<Unsigned> rhs) -> gray_code<Unsigned> { return add(lhs, rhs, base2(rhs)); } 

The Law of Useful Return

I was reading a book from Alexander Stepanov and Daniel Rose a few weeks ago and came across a paragraph about what they call The Law of Useful Return (ok, it was probably not that capitalized). Basically, it states that once you have computed something that could be reused in a function, even if it wasn't the aim of this function, you should not waste it - provided it can be reused - but return it along with the main results.

In our case, we have a recursive call to add and we compute the base2 of its result. If we look at the code closely, we can see that we almost always have the base when returning a result of an addition, and it is generally trivial to compute when we don't have it. That means that we can return the base along with the result instead of recomputing it after the recursive call:

// Return a pair of Gray codes where second is the result of // the addition, and first is the base2 of the result template<typename Unsigned> auto add(gray_code<Unsigned> lhs, gray_code<Unsigned> rhs, gray_code<Unsigned> rhs_base) -> std::pair<gray_code<Unsigned>, gray_code<Unsigned>> { auto lhs_base = base2(lhs); if (lhs_base == rhs_base) { if (lhs == rhs) { return { base2(lhs << 1u), (lhs << 1u) ^ is_odd(lhs) }; } return { (lhs_base << 1u), (lhs_base << 1u) ^ ((lhs_base ^ lhs) + (lhs_base ^ rhs)) }; } if (lhs_base.value < rhs_base.value) { std::swap(lhs, rhs); std::swap(lhs_base, rhs_base); } if (lhs == lhs_base) { return { lhs, lhs ^ rhs }; } // Get both the result of the addition and its base auto tmp = add(lhs ^ lhs_base, rhs, rhs_base); if (tmp.first.value < lhs_base.value) { return { lhs_base, lhs_base ^ tmp.second }; } return { (lhs_base << 1u), (lhs_base << 1u) ^ (lhs_base ^ tmp.second) }; } template<typename Unsigned> auto operator+(gray_code<Unsigned> lhs, gray_code<Unsigned> rhs) -> gray_code<Unsigned> { return add(lhs, rhs, base2(rhs)).second; } 

As we can see, computing the base and returning it with the result is almost always trivial, generally costing no more than a shift, probably optimized out by the compiler since it is used to compute the result anyway. The only case where computing the base is actually more expensive than computing the result is when lhs == rhs, but we can safely assume that lhs and rhs will be different from each other more often than not (and we stripped the potentially expensive ^ is_odd from the base calculation anyway since altering the least significant bit does not change the resulting base). On average, we do less computations by returning and reusing this additional value.

Special case when needed

Sometimes, adding more branches helps. Generally not - as pointed by @Emily -, that's why many potentially interesting observations I made about Gray codes didn't end up in this algorithm. However, it seems that checking whether lhs.value == 1u or whether rhs.value == 1u in operator+ (not in add) yields better results overall:

template<typename Unsigned> auto operator+(gray_code<Unsigned> lhs, gray_code<Unsigned> rhs) -> gray_code<Unsigned> { if (lhs.value == 1u) { return ++rhs; } if (rhs.value == 1u) { return ++lhs; } return add(lhs, rhs, base2(rhs)).second; } 

Why is it globally faster? I have several potential explanations, none that I tried to prove, may you may be interested in hearing them anyway:

• operator++ can be lightning fast for Gray codes since it only checks for the parity before flipping a bit. It is probably only that fast on architectures that store a parity bit though:

  template<typename Unsigned> auto operator++(gray_code<Unsigned> gray) -> gray_code<Unsigned> { if (is_odd(gray)) { auto y = gray.value & -gray.value; gray.value ^= (y << 1u); } else { gray.value ^= 1u; } return gray; } 

• The algorithm decomposes number into powers of \$2\$ and more generally into incrementally smaller powers of \$2\$. Since \$1 = 2^0\$, it may be one of the most encountered values in the algorithm.

• Since we put it in operator+ and not in add, it directly shortcuts everything and avoids some potentially expensive base computations since it would introduce a new case where computing the base is not as trivial as a shift.

Generally speaking, these optimizations don't come from nowhere: I tried each of them separately and probably tried most of the possible combinations, including putting the special cases in add too or in add only, etc... The combination of the four optimizations I provided in this answer is the one that yielded the fastest code for most results. However, it may still depend on the speed of the parity intrinsic provided by the compiler (when there is one). Interesting things, but not as generic as they could be.

A more meaningful name for base2

I mentioned in the question that base2 sounded like an awful name and therefore I tried to find a mathematical name for the function, especially avoiding references to bits since we are not dealing with a regular integer representation. And by "trying to find a better name", I actually mean that I asked the question on Mathematics.SE.

There have been some interesting terms (for example binadic floor, I really liked that one), but in the end someone managed to find a name and a symbol already in use for the function: for a number \$x\$, the number \$2^n\$ such as \$2^n \leq x < 2^{n+1}\$ is called the hyperfloor of \$x\$ and denoted \$\lfloor \lfloor x \rfloor \rfloor\$. Note that the function can also be read as \$2^{\lfloor \log_2 x \rfloor}\$ which is terser than my original description.

Also note that my implementation of base2 does note strictly compute \$\lfloor \lfloor x \rfloor \rfloor\$ since it may give different results for \$x < 1\$.