1 #ifndef DIVISIONBYCONST_HH
2 #define DIVISIONBYCONST_HH
28 [[nodiscard]]
inline uint32_t
getDivisor()
const {
return divisor; }
30 [[nodiscard]] uint32_t
div(uint64_t dividend)
const
32 #if defined __x86_64 && !defined _MSC_VER
33 uint64_t
t = (__uint128_t(dividend) * m + a) >> 64;
40 [[nodiscard]]
inline uint32_t
divinC(uint64_t dividend)
const
42 uint64_t t1 = uint64_t(uint32_t(dividend)) * uint32_t(m);
43 uint64_t t2 = (dividend >> 32) * uint32_t(m);
44 uint64_t t3 = uint32_t(dividend) * (m >> 32);
45 uint64_t t4 = (dividend >> 32) * (m >> 32);
47 uint64_t s1 = uint64_t(uint32_t(a)) + uint32_t(t1);
48 uint64_t s2 = (s1 >> 32) + (a >> 32) + (t1 >> 32) + t2;
49 uint64_t s3 = uint64_t(uint32_t(s2)) + uint32_t(t3);
50 uint64_t s4 = (s3 >> 32) + (s2 >> 32) + (t3 >> 32) + t4;
52 uint64_t result = s4 >> s;
55 assert(result == uint32_t(result));
57 return uint32_t(result);
60 [[nodiscard]] std::pair<uint32_t, uint32_t>
divMod(uint64_t dividend)
const
62 assert(uint32_t(divisor) == divisor);
63 uint64_t q =
div(dividend);
64 assert(uint32_t(q) == q);
66 uint32_t r = uint32_t(dividend) - uint32_t(q) * uint32_t(divisor);
70 [[nodiscard]] uint32_t
mod(uint64_t dividend)
const
72 auto [q, r] =
divMod(dividend);
Helper class to divide multiple times by the same number.
uint32_t div(uint64_t dividend) const
uint32_t divinC(uint64_t dividend) const
uint32_t mod(uint64_t dividend) const
std::pair< uint32_t, uint32_t > divMod(uint64_t dividend) const
uint32_t getDivisor() const
void setDivisor(uint32_t divisor)
This file implemented 3 utility functions: