diff options
author | ExMix <rahuba.youri@mapswithme.com> | 2014-08-13 15:19:13 +0400 |
---|---|---|
committer | Alex Zolotarev <alex@maps.me> | 2015-09-23 02:24:46 +0300 |
commit | 3587e8ccc934fca003a04906f154c7d9ec43cb44 (patch) | |
tree | 604aedf9f2dd38a31635969ddfc4988654fc5d42 /base/math.hpp | |
parent | 3f76c76d045438a5024a347bf80de2b51fddb9e6 (diff) |
[core] greatest common divisor and tests
Diffstat (limited to 'base/math.hpp')
-rw-r--r-- | base/math.hpp | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/base/math.hpp b/base/math.hpp index f1eed73e8b..41614af7a4 100644 --- a/base/math.hpp +++ b/base/math.hpp @@ -139,4 +139,49 @@ inline uint32_t NextPowOf2(uint32_t v) return v + 1; } +// Greatest Common Divisor +inline uint32_t GCD(uint32_t a, uint32_t b) +{ + uint32_t multiplier = 1; + uint32_t gcd = 1; + while (true) + { + if (a == 0 || b == 0) + { + gcd = max(a, b); + break; + } + + if (a == 1 || b == 1) + { + gcd = 1; + break; + } + + if ((a & 0x1) == 0 && (b & 0x1) == 0) + { + multiplier <<= 1; + a >>= 1; + b >>= 1; + continue; + } + + if ((a & 0x1) != 0 && (b & 0x1) != 0) + { + uint32_t minV = min(a, b); + uint32_t maxV = max(a, b); + a = (maxV - minV) >> 1; + b = minV; + continue; + } + + if ((a & 0x1) != 0) + swap(a, b); + + a >>= 1; + } + + return multiplier * gcd; +} + } |