>>881
>>887
足算だけ実装すれば大丈夫ですよ。
a=1
b=0;
を初期値にして
2進数で下の桁から見ながら
２進数のその桁が1ならb=a+b;
その後、 a=a+a;