arith

// vi:set ft=cpp: -*- Mode: C++ -*-
/*
 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>
 *     economic rights: Technische Universität Dresden (Germany)
 *
 * License: see LICENSE.spdx (in this directory or the directories above)
 */
 
#pragma once
 
namespace cxx { namespace arith {
 
template<typename N, typename D>
constexpr N
div_ceil(N const &n, D const &d)
{
  // Since C++11 the "quotient is truncated towards zero (fractional part is
  // discarded)". Thus a negative quotient is already ceiled, whereas a
  // positive quotient is floored. Furthermore, since C++11 the sign of the
  // % operator is no longer implementation defined, thus we can use n % d to
  // detect if the quotient is positive (n % d >= 0) and was truncated (n % d !=
  // 0). In that case, we add one to round to the next largest integer.
  return n / d + (n % d > 0);
}
 
template< unsigned long V >
struct Ld
{
  enum { value = Ld<V / 2>::value + 1 };
};
struct Ld {…};
 
template<>
struct Ld<0>
{
  enum { value = ~0UL };
};
 
template<>
struct Ld<1>
{
  enum { value = 0 };
};
 
constexpr unsigned
log2u(unsigned val)
{
  return 8 * sizeof(val) - __builtin_clz(val) - 1;
}
 
constexpr unsigned
log2u(unsigned long val)
{
  return 8 * sizeof(val) - __builtin_clzl(val) - 1;
}
 
constexpr unsigned
log2u(unsigned long long val)
{
  return 8 * sizeof(val) - __builtin_clzll(val) - 1;
}
 
template<typename T>
constexpr unsigned
log2u_ceil(T val)
{
  return val == 1 ? 0 : log2u(val - 1) + 1;
}
 
}}
namespace cxx { namespace arith {…}