# Bitwise GCD Challenge

Write the shortest iterative function to find gcd of two numbers (assume 32 bit numbers).

Rules:

• Arithmetic, Comparison and Logical Operators are not allowed (except equality comparison (a==b) operator).
• Function should work for both positive and negative numbers
• No inbuilt functions allowed.
• All bitwise operators allowed.
• What is allowed in the loop head? Only zero-test? – John Dvorak Oct 19 '13 at 6:21
• @JanDvorak Can be anything, but within the limit of the rules – Coding man Oct 19 '13 at 6:27
• ok, does equality test count as comparison, or do we have to do a poor-man's XOR followed by a zero-check? – John Dvorak Oct 19 '13 at 6:39
• @JanDvorak No comparison operator allowed. You can use your second idea. – Coding man Oct 19 '13 at 6:44
• @JanDvorak Unfortunately XOR is also not allowed and has to be replaced by (a|b)&!(a&b). Together with no comparisons allowed this seems rather arbitrary to me and disqualifies lots of languages. Not interesting. – Howard Oct 19 '13 at 9:01

## Python - 196 bytes

def A(a,b):
while b:a,b=a&~b|~a&b,(a&b)<<1
return a
def G(a,b,i=0):
if a>>31:a=A(~a,1)
if b>>31:b=A(~b,1)
while~a&b|a&~b:c,d=~a&1,~b&1;i=A(i,c&d);a,b=[b,a>>c,A(a,b),b>>d][c|d::2]
return a<<i


Sample usage:

from random import randint
for i in range(10):
a = randint(-2147483647,2147483647)
b = randint(-2147483647,2147483647)
print 'gcd(%d, %d) = %d'%(a, b, G(a,b))


Sample output:

gcd(-36916085, -1872111029) = 1
gcd(1355889652, 1816917540) = 188
gcd(-366482295, 1612196424) = 9
gcd(836632083, -1156302534) = 3
gcd(1223074731, -1299765354) = 123
gcd(-1154829176, 522085100) = 4
gcd(-1673024403, 1589241938) = 1
gcd(-1871498822, -1089342630) = 2
gcd(1653429392, 2095617430) = 2
gcd(1525670601, -1985869899) = 39


### Implementation Notes

• A -> a function which adds two integers.
• a&~b|~a&b -> a^b
• if a>>31 -> if a<0
• a=A(~a,1) -> a=-a (taken together, if a>>31:a=A(~a,1) -> a=abs(a))
• ~a&1 -> a%2==0 a.k.a. a is even.

The function G begins by removing powers of 2 from both a and b (and shifting the result if both are even). When both a and b are odd, it continues on with a=b, b=(a+b)/2. This works because gcd(a, b) = gcd(a, a+b), and a+b is necessarily even. This would terminate noticeably sooner using a comparison and a subtraction (subtracting the smaller value from the larger), but neither are available.

• great!!, first to answer – Coding man Oct 19 '13 at 9:15
• you are using recursion, please do it iteratively.. – Coding man Oct 19 '13 at 9:32
• please, verify if the description was ambiguous "Write the shortest iterative function to find gcd of two numbers". If ambiguous, recursion will be fine and I will update the question else you have to update the code :P – Coding man Oct 19 '13 at 9:49
• I apologize. I must have skipped over the word 'iterative' while reading the description. – primo Oct 19 '13 at 10:02