Binary GCD
(Mylib/Number/binary_gcd.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

References

Verified with

• test/aoj/NTL_1_C/main.test.cpp

Code

#pragma once
#include <cmath>
#include <utility>

namespace haar_lib {
  int64_t binary_gcd(int64_t a, int64_t b) {
    int64_t g = 1;

    while (1) {
      if (a > b) std::swap(a, b);

      if (a == 0) {
        break;
      } else {
        if ((a & 1) == 0 and (b & 1) == 0) {
          a >>= 1;
          b >>= 1;
          g <<= 1;
        } else if ((a & 1) == 0) {
          a >>= 1;
        } else if ((b & 1) == 0) {
          b >>= 1;
        } else {
          int64_t t = std::abs(a - b) >> 1;
          b         = t;
        }
      }
    }

    return g * b;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/binary_gcd.cpp"
#include <cmath>
#include <utility>

namespace haar_lib {
  int64_t binary_gcd(int64_t a, int64_t b) {
    int64_t g = 1;

    while (1) {
      if (a > b) std::swap(a, b);

      if (a == 0) {
        break;
      } else {
        if ((a & 1) == 0 and (b & 1) == 0) {
          a >>= 1;
          b >>= 1;
          g <<= 1;
        } else if ((a & 1) == 0) {
          a >>= 1;
        } else if ((b & 1) == 0) {
          b >>= 1;
        } else {
          int64_t t = std::abs(a - b) >> 1;
          b         = t;
        }
      }
    }

    return g * b;
  }
}  // namespace haar_lib

Back to top page