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

質問

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 · ベストアンサー

ちょっとおもしろそうなので、やってみました。
四則演算を使わないというふうに勝手に判断して書いてみました。

#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);
}

お礼

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

回答No.5

nag0720

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

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

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

回答No.4

wormhole

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

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

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

#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は計算しないようにしてください。
ここで苦労してます。

回答No.2

honor

比較はしてないのでどちらが早いかは分かりませんが、
奇数ビットと偶数ビットの繰り上がりを分けて出すのは如何ですか。

お礼

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

回答No.1

Tacosan

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

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

お礼

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