Since numbers are naturally binary, dividing even numbers by two does not count as division.
Count the number of zeros at the right of both numbers.
Call the minimum of these counts R.
Shift both numbers right R bits.
(The answer is 2^{R} times the GCD of the two new numbers.)
If one of the numbers is even shift it right until it is odd.
This does not change the GCD of the two.
We have two odd numbers and we repeat the following:

- Subtract the two numbers giving a third which will be even.
If the new number is zero, either of the others, times 2

The number of steps is somewhat larger than for Euclid’s algorithm, but subtracting and shifting are much faster than division. Perhaps I learned this from Knuth’s Semi-Numerical Algorithms where he considers the performance of this algorithm.