************************** :mod:`gray` --- Gray codes ************************** .. module:: gray 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. .. cpp:class:: gray_code This class takes a built-in unsigned integer type ``T`` as a template parameter. If any other type is passed, the compilation ill fail with an error message. .. cpp:type:: gray_code::value_type This is an alias for the underlying unsigned integer type ``T``. .. cpp:member:: gray_code::value_type gray_code::value This is the underlying unsigned integer value whose bits are in Gray code order. 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. .. cpp:function:: gray_code::gray_code() noexcept Default constructor. It initializes the underlying value with :math:`0`. There is no dedicated way to construct an uninitialized ``gray_code`` instance. .. cpp:function:: explicit gray_code::gray_code(value_type value) noexcept Takes an instance of the underlying type and converts it to a Gray code. Note that ``gray_code`` is not meant to « be an integer », therefore all the conversions to and from the underlying type are ``explicit`` so that none of the types is considered more important than the other. It may sound quite philosophical, but that's it. .. cpp:function:: explicit gray_code::gray_code(bool value) noexcept The Gray code and base :math:`2` representations for the numbers :math:`0` and :math:`1` are the same. Therefore, an ``explicit`` construction from a boolean type makes sense and is guaranteed not to perform any conversion. 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. .. cpp:function:: gray_code& operator=(value_type other) & noexcept Assigns an instance of its underlying type to the Gray code. .. cpp:function:: gray_code& operator=(bool other) & noexcept Assigns a boolean to the Gray code. 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`` and a ``gray_code`` 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. .. cpp:function:: explicit gray_code::operator value_type() const noexcept Converts the Gray code into its regular base :math:`2` representation. .. cpp:function:: constexpr explicit gray_code::operator bool() const noexcept Converts the Gray code into a boolean. This function will return ``false`` if the Gray code is equal to :math:`0` and ``true`` otherwise. 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. .. cpp:function:: constexpr bool operator==(gray_code lhs, gray_code rhs) noexcept .. cpp:function:: constexpr bool operator!=(gray_code lhs, gray_code rhs) noexcept .. cpp:function:: constexpr bool operator==(gray_code lhs, T rhs) noexcept .. cpp:function:: constexpr bool operator!=(gray_code lhs, T rhs) noexcept .. cpp:function:: constexpr bool operator==(T lhs, gray_code rhs) noexcept .. cpp:function:: constexpr bool operator!=(T lhs, gray_code rhs) noexcept I don't have a fast algorithm for Gray codes rich comparisons (`<`, `<=`, `>=`, `>`), so the richer comparison operators are not defined. 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: .. cpp:function:: gray_code operator&(gray_code lhs, gray_code rhs) noexcept .. cpp:function:: gray_code operator|(gray_code lhs, gray_code rhs) noexcept .. cpp:function:: gray_code operator^(gray_code lhs, gray_code rhs) noexcept .. cpp:function:: gray_code operator~(gray_code rhs) The bitwise assignment operations are also overloaded between Gray codes: .. cpp:function:: gray_code& gray_code::operator&=(gray_code other) noexcept .. cpp:function:: gray_code& gray_code::operator|=(gray_code other) noexcept .. cpp:function:: gray_code& gray_code::operator^=(gray_code other) noexcept Additionally, the bitwise assignment operations can be performed between a Gray code and its underlying type, in both directions: .. cpp:function:: gray_code& gray_code::operator&=(value_type other) noexcept .. cpp:function:: gray_code& gray_code::operator|=(value_type other) noexcept .. cpp:function:: gray_code& gray_code::operator^=(value_type other) noexcept .. cpp:function:: T& operator&=(T& lhs, gray_code rhs) noexcept .. cpp:function:: T& operator|=(T& lhs, gray_code rhs) noexcept .. cpp:function:: T& operator^=(T& lhs, gray_code rhs) 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``: .. cpp:function:: gray_code& gray_code::operator&=(bool other) noexcept .. cpp:function:: gray_code& gray_code::operator|=(bool other) noexcept .. cpp:function:: gray_code& gray_code::operator^=(bool other) noexcept .. cpp:function:: gray_code operator&(gray_code lhs, bool rhs) noexcept .. cpp:function:: gray_code operator&(bool lhs, gray_code rhs) noexcept .. cpp:function:: gray_code operator|(gray_code lhs, bool rhs) noexcept .. cpp:function:: gray_code operator|(bool lhs, gray_code rhs) noexcept .. cpp:function:: gray_code operator^(gray_code lhs, bool rhs) noexcept .. cpp:function:: gray_code operator^(bool lhs, gray_code rhs) noexcept 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: .. cpp:function:: gray_code& gray_code::operator>>=(std::size_t shift) noexcept .. cpp:function:: gray_code& gray_code::operator<<=(std::size_t shift) noexcept .. cpp:function:: gray_code operator>>(gray_code value, std::size_t shift) noexcept .. cpp:function:: gray_code operator<<(gray_code value, std::size_t shift) noexcept 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 :math:`2` representation, performing an operation and converting the result back to a Gray code. The following arithmetic operations are defined on Gray codes: .. cpp:function:: gray_code& gray_code::operator++() noexcept .. cpp:function:: gray_code gray_code::operator++(int) noexcept .. cpp:function:: gray_code& gray_code::operator--() noexcept .. cpp:function:: gray_code gray_code::operator--(int) noexcept 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. .. cpp:function:: bool is_even(gray_code 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_parity`` intrinsic 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 :math:`2` in some cases, so it is possible that the ``gray_code`` operations are slower than the naive ones on an architecture that does not store the parity bit. .. cpp:function:: bool is_odd(gray_code code) noexcept Returns whether a Gray code is odd. Miscellaneous functions ----------------------- .. cpp:function:: constexpr gray_code gray(T value) noexcept Construction function. Deduces the type of the parameter (only unsigned types are accepted) and returns a ``gray_code`` with the corresponding underlying type. .. cpp:function:: void swap(gray_code& lhs, gray_code& rhs) noexcept Swaps two Gray codes by swapping their ``value`` member. .. _Gray code: https://en.wikipedia.org/wiki/Gray_code