digit_arithmetic.hpp

Go to the documentation of this file.

/**
 * @file digit_arithmetic.hpp
 * @author Charles Karney <charles.karney@sri.com>
 * @brief Definition of digit_arithmetic
 *
 * Copyright (c) Charles Karney (2014-2020) and licensed under the MIT/X11
 * License.  For more information, see http://exrandom.sourceforge.net/
 */

#if !defined(EXRANDOM_DIGIT_ARITHMETIC_HPP)
#define EXRANDOM_DIGIT_ARITHMETIC_HPP 1

#include <cstdint>              // for uint_fast32_t
#include <limits>               // for numeric_limits<uint_t>::digits;

#include <exrandom/exrandom_config.hpp>

/**
 * @brief The common namespace.
 *
 * The entire library resides in this namespace so avoid the possibility of
 * name conflicts.  For the same reason, all the headers are in the exrandom
 * directory in the include path.
 */
namespace exrandom {

  /**
   * @relates digit_arithmetic
   * The unsigned type used for random digits.
   */
  typedef std::uint_fast32_t uint_t;

  /**
   * @relates digit_arithmetic
   * The size of uint_t in bits.
   */
  const int uint_w = std::numeric_limits<uint_t>::digits;

  /**
   * @relates digit_arithmetic
   * A mask for uint_t.
   */
  const uint_t uint_m = 0xffffffffUL;

  /**
   * @relates digit_arithmetic
   * @param x
   * @return the position of the most significant bit in @e x.
   *
   * returns 0 for @e x = 0, 32 for @e x = uint_m
   */
  constexpr int highest_bit_idx(unsigned x)
  { return x == 0 ? 0 : 1 + highest_bit_idx(x >> 1); }

  /**
   * @brief Machinery to manipulate bases.
   *
   * @tparam b the base as an unsigned.
   *
   * Base @e b = 0 is treated as 2<sup>32</sup>. @e b = 1 is disallowed.
   */
  template<uint_t b> class digit_arithmetic {
  public:
    /**
     * The base (or 0 if the base is 2<sup>32</sup>).
     */
    static const uint_t base = b & uint_m;
    /**
     * The base less 1, in range [1, 2<sup>32</sup> &minus; 1].
     */
    static const uint_t basem1 = base ? base - 1UL : uint_m;
    /**
     * The number of bits needed to hold a digit in [0, @e basem1].
     */
    static const int bits = highest_bit_idx(unsigned(basem1));

    /**
     * Is the base a power of 2?
     */
    static const bool power_of_two =
              basem1 == (bits == uint_w ? ~uint_t(0) :
                      ~(~uint_t(0) << (bits < uint_w ? bits : 0)));
  private:
    // Require base > 1
    static_assert(bits != 0, "base must be 2 or more");
  };

}

#endif  // EXRANDOM_DIGIT_ARITHMETIC_HPP