按位GCD挑战
按位GCD挑战
提问于 2013-10-19 04:45:23
编写最短迭代函数，以求两个数字的gcd (假设32位数)。
规则：
- 不允许算术、比较和逻辑运算符(除相等比较(*
a==b**)运算符外)。 - 函数应该同时适用于正数和负数。
- 不允许内置函数。
- 所有按位运算符都允许。
回答 1
Code Golf用户
回答已采纳
发布于 2013-10-19 09:05:18
Python-196字节
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样本使用情况：
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))样本输出：
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实现说明
A->是一个添加两个整数的函数.a&~b|~a&b->a^bif a>>31->if a<0a=A(~a,1)->a=-a(综合起来，if a>>31:a=A(~a,1)->a=abs(a))~a&1->a%2==0a.k.a.a是平的。
函数G首先从a和b中移除2的幂(如果两者都是偶数，则移除结果)。当a和b都是奇数时，就会继续使用a=b, b=(a+b)/2。这是因为gcd(a, b) = gcd(a, a+b)和a+b必须是平的。使用比较和减法(从较大的值中减去较小的值)，这将明显地提前终止，但两者都不可用。
页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/12897
复制相关文章
相似问题
腾讯云开发者
