加算の繰り上がり部分を高速に計算

int型の変数a,bの加算を行う場合、
繰り上がり部分の処理が面倒ですが、
以下のようなコードを書きました。
cが繰り上がり部分となります。

#include <stdio.h>

int main()
{
int a=1111;
int b=458778;
int N=31;
int c=0;
int flg=0;
int bit=1;

for(int i=0;i<N;i++){

if(flg)c^=bit;

int ai=a & bit;
int bi=b & bit;

if(!flg && ai && bi)flg=1;
else if(flg && !ai && !bi){
flg=0;
}

bit<<=1;
}

printf("%d\n",a+b);
printf("%d\n",a^b^c);
}

この処理を可能な限り早く行いたいのですが、
どのような手法があるでしょうか？

No.6 ベストアンサー 回答者： ki073 回答日時： 2013/08/25 17:45

ちょっとおもしろそうなので、やってみました。

四則演算を使わないというふうに勝手に判断して書いてみました。

#define N 31

inline int fn1(int a, int b)
{
int c=0;
int flg=0;
int bit=1;
for(int i=0;i<N;i++){
int ai=a & bit;
int bi=b & bit;
flg = ((ai & bi) | (ai & flg) | (bi & flg));
flg<<=1;
c|=flg;
bit<<=1;
}
return c;
}

ついでに計算時間も計りました。（10000000回ループを回したときの時間です）
上のプログラム　0m0.653s
No.4のプログラム　0m0.798s
質問欄のプログラム　0m2.327s

一般的な高速化の方法ですが、
1) if文などの条件判断をLoopの中から極力排除する。(パイプラインの関係)
2) テーブル引きを、可能なら関数などレジスタで計算できるようにする。
3) ここでは使っていませんが、ループのデータ依存関係を排除する　（SSEなどベクトル演算ができる）
などです。測定プログラムを書いておきます。
乱数で数値を発生させています。またsumをちょっと余分につけています。結果をその都度出力していたら、出力の時間を計っているようになるので、それとコンパイラによっては最適化で計算を省略することを防ぐためです。
ちなみに、randやsumの関数の計算と関係ない以部分は0m0.182sです。

#include <stdio.h>
#include <stdlib.h>
int main()
{
int a, b, c;
int sum=0;
for(int j=0; j<10000000; j++){
a=rand()/4;
b=rand()/4;
c=fn2(a, b);
sum=sum+c;
}
printf("%d\n",sum);
}

この回答へのお礼

ありがとうございます。
確認いたしました。速いですね。

お礼日時：2013/08/25 19:01

No.5 回答者： nag0720 回答日時： 2013/08/25 17:14

１ビット単位で繰上げの判定をしたいということでしょうか？

１ビット単位が原則なら、質問文のプログラムのようにif文で判定するか、No.4さんのように配列を使うか、もしくは、ビット論理式で計算するしかないでしょう。

なぜa ^ bを計算してはいけないのか分かりませんが、２ビット単位とか、４ビット、８ビット単位で計算することもだめなのでしょうか。

No.4 回答者： wormhole 回答日時： 2013/08/25 11:36

早いかどうかわかりませんけど。

int carray_tbl[][][] = {
{ { 0, 0 }, { 0, 1 } }, { { 0, 1 }, { 1, 1 } },
};

int main()
{
int a = 1111;
int b = 458778;
int c = 0;
int N = 31;

int ta = a;
int tb = b;
int cf = 0;
for (int i = 0; i < N; i++) {
cf = carray_tbl[ta & 1][tb & 1][cf];
ta >>= 1;
tb >>= 1;
c |= cf << (i + 1);
}

printf("%d\n", c);
return 0;
}

No.3 回答者： yaemon_2006 回答日時： 2013/08/25 08:18

早いかどうかわからないけど、

#include <stdio.h>

int main(void)
{
int a = 1, b = 2, c, f;

c = a ^ b;
f = (a & b) << 1;
while(f){
int d = (c ^ f);

f = (c & f) << 1;
c = d;
}
printf("%d + %d = %d\n", a, b, c);
return 0;
}

この回答へのお礼

重要なことをお伝えするのを忘れてました。
a ^ bは計算しないようにしてください。
ここで苦労してます。

お礼日時：2013/08/25 08:46

No.2 回答者： honor 回答日時： 2013/08/25 05:27

比較はしてないのでどちらが早いかは分かりませんが、

奇数ビットと偶数ビットの繰り上がりを分けて出すのは如何ですか。

この回答へのお礼

なるほど。考えてみます。

お礼日時：2013/08/25 08:47

No.1 回答者： Tacosan 回答日時： 2013/08/25 03:07

「int型の変数a,bの加算を行う」なら素直に a+b と書けばいい.

なぜこんな面倒くさいことを考える?

この回答へのお礼

詳細は申し上げられませんが、仕事上の理由です。

お礼日時：2013/08/25 08:39