binary greatest common divisor

bgcd.go

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	fmt.Println(bgcd(6, 36))
	fmt.Println(bgcd(2, 36))
	fmt.Println(bgcd(3, 9))
	fmt.Println(bgcd(3, 5))
}

func ctz(u uint32) uint32 {
	return uint32(bits.TrailingZeros32(u))
}

func ctz(u uint32) uint32 {
    return uint32(bits.TrailingZeros32(u))
}

func bgcd(a, b uint32) uint32 {
    if a == 0 || b == 0 {
        return a | b
    }
    s := ctz(a | b)
    for ; b > 0; b -= a {
        a >>= ctz(a)
        b >>= ctz(b)
        if a > b {
            a, b = b, a
        }
    }
    return a << s
}