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ベストアンサー
- 回答日時:
ちょっとおもしろそうなので、やってみました。
四則演算を使わないというふうに勝手に判断して書いてみました。
#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
- 回答日時:
1ビット単位で繰上げの判定をしたいということでしょうか?
1ビット単位が原則なら、質問文のプログラムのようにif文で判定するか、No.4さんのように配列を使うか、もしくは、ビット論理式で計算するしかないでしょう。
なぜa ^ bを計算してはいけないのか分かりませんが、2ビット単位とか、4ビット、8ビット単位で計算することもだめなのでしょうか。
No.4
- 回答日時:
早いかどうかわかりませんけど。
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
- 回答日時:
早いかどうかわからないけど、
#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;
}
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語での引数の省略方法
-
「指定されたキャストは有効で...
-
#define _CRT_SECURE_NO_WARNIN...
-
ファイルに含まれるアルファベ...
-
数字列を3桁ごとにカンマで区切...
-
演算子オーバーロードのプログ...
-
C言語 エラーの原因がわからな...
-
市松模様
-
ラップ関数とはどんなものですか?
-
【C++】関数ポインタの使い方
-
c言語 〇×ゲーム
-
C言語初心者です、、、お助けく...
-
アスタリスクで正方形
-
足して100になるような乱数のア...
-
std::set<int> で、ある値が何...
-
acceptをalarmでタイムアウトさ...
-
複数桁10進数の*桁目だけを抽出...
-
(マルチスレッド)_beginthrea...
-
C言語で三目並べをするプログラ...
-
C++でvectorにテキストファイル...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「指定されたキャストは有効で...
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語 エラーの原因がわからな...
-
複数桁10進数の*桁目だけを抽出...
-
【C++】関数ポインタの使い方
-
std::set<int> で、ある値が何...
-
ラップ関数とはどんなものですか?
-
実数の整数部,小数部の取得
-
if と配列の組み合わせ
-
「{ } で囲むだけ」は正しい?
-
return 1L
-
足して100になるような乱数のア...
-
C言語
-
(int *)の意味
-
system関数がうまくいかない
-
構造体の勉強中です 合計点の高...
-
C言語で分からないところがあり...
-
PowerShellがうまくいかない
-
課題でつまってます・・・
おすすめ情報