5. gray — Gray codes¶
This module defines a class that represents Gray code. The Gray code, or binary reflected code is a binary numeral system invented by Frank Gray where every value differs from its neighbours by only one bit. Gray codes have several applications in computer programming and can notably be used in the field of genetic algorithms.
Note that specific operations on Gray codes are defined in this module if and only if they are faster than converting the Gray codes to regular integers, performing an operation on integers and converting the result back to a Gray code. Therefore, you might notice that every bitwise operation is define while only some arithmetic operations are defined, such as increment and decrement.
-
class
gray_code<T>¶ This class takes a built-in unsigned integer type
Tas a template parameter. If any other type is passed, the compilation ill fail with an error message.
-
type
gray_code<T>::value_type¶ This is an alias for the underlying unsigned integer type
T.
-
gray_code<T>::value_type
gray_code<T>::value¶ This is the underlying unsigned integer value whose bits are in Gray code order.
5.1. Construction functions¶
Gray codes can be default-constructed or constructed from an instance of the underlying type or from a boolean. As of now, there isn’t any function to create a Gray code directly with its underlying value without a conversion.
-
gray_code<T>::gray_code() noexcept¶ Default constructor. It initializes the underlying value with \(0\). There is no dedicated way to construct an uninitialized
gray_codeinstance.
-
explicit
gray_code<T>::gray_code(value_type value) noexcept¶ Takes an instance of the underlying type and converts it to a Gray code. Note that
gray_codeis not meant to « be an integer », therefore all the conversions to and from the underlying type areexplicitso that none of the types is considered more important than the other. It may sound quite philosophical, but that’s it.
-
explicit
gray_code<T>::gray_code(bool value) noexcept¶ The Gray code and base \(2\) representations for the numbers \(0\) and \(1\) are the same. Therefore, an
explicitconstruction from a boolean type makes sense and is guaranteed not to perform any conversion.
5.2. Assignment operations¶
Basically, a gray_code can be assignment an instance from any type it can be constructed
with. Moreover, the assignment operations that are not automatically generated by the compiler
are lvalue-qualified so that expressions of the form (a & b) = c are prohibited directly
at compile time.
5.3. Conversion operations¶
Gray codes can be converted to their underlying type or to a boolean. Such a conversion is
always explicit. Contrary to regular integers, there is no conversion allowed between a
gray_code<unsigned> and a gray_code<unsigned long> for example. All conversions are
explicit so that there are no unexpected conversions while trying to perform a bitwise
operation between a Gray code and an instance of its underlying type for example.
-
explicit
gray_code<T>::operator value_type() const noexcept¶ Converts the Gray code into its regular base \(2\) representation.
-
explicit constexpr
gray_code<T>::operator bool() const noexcept¶ Converts the Gray code into a boolean. This function will return
falseif the Gray code is equal to \(0\) andtrueotherwise.
5.4. Comparison operations¶
The equality operations are defined between Gray codes and between a Gray code and its underlying type. Those are arithmetic comparison operations, not bitwise comparison operations; a Gray is still an integer, albeit with a different bit representation.
I don’t have a fast algorithm for Gray codes rich comparisons (<, <=, >=, >), so the richer comparison operators are not defined.
5.5. Bitwise operations¶
One of the main interests of Gray codes is their binary representation. Therefore,
the class gray_code overloads the basic bitwise operators so that they work as
expected in the most simple cases. First of all, these operators are overloaded to
work between instances of the same gray_code specialization:
The bitwise assignment operations are also overloaded between Gray codes:
Additionally, the bitwise assignment operations can be performed between a Gray code and its underlying type, in both directions:
-
gray_code<T> &
gray_code<T>::operator&=(value_type other) noexcept¶
-
gray_code<T> &
gray_code<T>::operator|=(value_type other) noexcept¶
-
gray_code<T> &
gray_code<T>::operator^=(value_type other) noexcept¶
Note that no type is more important than the other one between a gray_code and its
underlying type, we don’t define operator&, operator| and operator^ between
a Gray code and its underlying type. Since both types are equally important, there is
no way we can choose a proper return type between the two of them without discrimination.
If you want to perform a bitwise operation, either use two variables of the same type or
use the compound assignment operators.
However, the bitwise operations are defined with bool and make gray_code more
important than bool (just like a bitwise operation between an unsigned and a
bool will yield an unsigned instance). Compound assignment operations with a
boolean on the left-hand side are not defined since they wouldn’t really make sense.
The following bitwise operations are defined between gray_code and bool:
Finally, the bitwise shift operations are also defined for gray_code. Modelled after
std::bitset, they can only take std::size_t on their right-hand side:
5.6. Arithmetic operations¶
As stated in the introduction, arithmetic operations are only implemented if they can be at least as fast if not even faster than converting the parameters to a base \(2\) representation, performing an operation and converting the result back to a Gray code. The following arithmetic operations are defined on Gray codes:
The incrementation and decrementation operators are circular, which means that if we try to increment the highest possible value for a type, we get the lowest possible value for this type, and it works the other way around for the decrementation.
-
bool
is_even(gray_code<T> code) noexcept¶ Returns whether a Gray code is even. A Gray code is even when its number of set bits is even. Therefore, when available, this function calls the
__builtin_parityintrinsic which should be fast on architectures that store the parity bit. Generally speaking, some algorithms rely on this operation to beat the double conversion to base \(2\) in some cases, so it is possible that thegray_codeoperations are slower than the naive ones on an architecture that does not store the parity bit.