Number_Theory/Binary-Gcd.hpp

• View this file on GitHub
• Last update: 2023-02-11 22:54:48+08:00
• Include: #include "Number_Theory/Binary-Gcd.hpp"

Depends on

• Template/Template.hpp

Required by

• Number_Theory/Factorization.hpp
• Number_Theory/Gauss-Integer.hpp
• Number_Theory/OsakDivisorsFast.hpp

Verified with

• Verify/Factorize.test.cpp

Code

#pragma once

#include "../Template/Template.hpp"

inline i64 binary_gcd(i64 a, i64 b) {
    if (a == 0 || b == 0) return a + b;
    char n = __builtin_ctzll(a);
    char m = __builtin_ctzll(b);
    a >>= n;
    b >>= m;
    n = std::min(n, m);
    while (a != b) {
        i64 d = a - b;
        char s = __builtin_ctzll(d);
        bool f = a > b;
        b = f ? b : a;
        a = (f ? d : -d) >> s;
    }
    return a << n;
}

#line 2 "Number_Theory/Binary-Gcd.hpp"

#line 2 "Template/Template.hpp"

#include <bits/stdc++.h>

using i64 = std::int64_t;
#line 4 "Number_Theory/Binary-Gcd.hpp"

inline i64 binary_gcd(i64 a, i64 b) {
    if (a == 0 || b == 0) return a + b;
    char n = __builtin_ctzll(a);
    char m = __builtin_ctzll(b);
    a >>= n;
    b >>= m;
    n = std::min(n, m);
    while (a != b) {
        i64 d = a - b;
        char s = __builtin_ctzll(d);
        bool f = a > b;
        b = f ? b : a;
        a = (f ? d : -d) >> s;
    }
    return a << n;
}

Back to top page