Binary GCD
(lib/others/binary_gcd.hpp)

• View this file on GitHub
• Last update: 2025-02-14 23:44:24+09:00
• Include: #include "lib/others/binary_gcd.hpp"

Code

#pragma once

/**
 * @brief Binary GCD
 */

template <typename T>
T binary_gcd(T a, T b) {
    unsigned long long x = a < 0 ? -a : a, y = b < 0 ? -b : b;
    if(!x || !y) return x + y;
    int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
    x >>= n, y >>= m;
    while(x != y){
        if(x > y){
            x = (x - y) >> __builtin_ctzll(x - y);
        } else{
            y = (y - x) >> __builtin_ctzll(y - x);
        }
    }
    return x << (n > m ? m : n);
}

#line 2 "lib/others/binary_gcd.hpp"

/**
 * @brief Binary GCD
 */

template <typename T>
T binary_gcd(T a, T b) {
    unsigned long long x = a < 0 ? -a : a, y = b < 0 ? -b : b;
    if(!x || !y) return x + y;
    int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
    x >>= n, y >>= m;
    while(x != y){
        if(x > y){
            x = (x - y) >> __builtin_ctzll(x - y);
        } else{
            y = (y - x) >> __builtin_ctzll(y - x);
        }
    }
    return x << (n > m ? m : n);
}

Back to top page