Q&A
本題ではありませんが、C言語で「x^n」はXOR演算です（ので、もとのビット幅に収まってしまいます）。さすがに勘違いする人はいないと思いますが、わかる書き方をしたほうがいいかなと思います。
※ 私はあまり数学は得意ではないです...
CやC++でやっています。(主にBetterCというやつです)
C言語(もしくはC++)でlong longを超える値を扱う場合、どのようにすべきでしょうか。
例えば (xのn乗)を計算する Test::factorial関数があるとして、これの型をどうするかです。
ある処理(例えば暗号等)をするライブラリを組んでいて、データ列(std::stringやstd::vector etc.)
の長さを指定したい時があります。
例えば暗号であれば「平文の長さは1～(2の64乗)とする」等のような場合で
Cipherクラスがあるとして Cipher::maxPlainTextLength() で(要求する平文の)最大の長さを返したい...とかです。
その場合、私のイメージでは
TYPE Cipher::maxPlainTextLength()
と考えています。(TYPEには型名が入りますが...)
ですが、実際に最小単位のサンプルコードで試すと 2^64 を計算するだけでもオーバーフローを起こします。
桁あふれをさせずに表示できないものでしょうか。
出来れば外部ライブラリは入れたくないのですが...
一応のコード。
C++
1// 必要なヘッダはインクルードしているとします... 2 3namespace Test{ 4 // 型が不明なため... 5 using TYPE = int; 6 7 // ans = x^n 8 Test::TYPE factorial( Test::TYPE x, Test::TYPE n ){ 9 Test::TYPE tmp = 1; 10 /* 11 計算式: 12 (2の3乗) = 2 * 2 * 2 = 8 13 (2の64乗) = 2 * 2 * 2 ... = 18446744073709551616 14 */ 15 for( int i = 0; i < (int)n; i++ ){ 16 tmp *= x; 17 //cout << i << ":" << tmp << endl; 18 } 19 return tmp; 20 } 21} 22 23int main( void ){ 24 Test::TYPE ans = Test::factorial( 2, 64 ); 25 std::cout << ans << std::endl; 26return 0; 27}
上記のコードを実行すると、なぜか0となります。
factorial 内のfor中で表示させると i = 30 辺りから負の数、
それ以降は 0になっているみたいです。
そして、ProgrammingPlace Plus というサイトでは(C言語編の第１９章の整数型辺り)
まず、符号無し整数型の方ですが、0 になりました。
これはつまり、最小値に戻ってきているということですが、
正確にいえば、表現できる最大値 + 1 で割った余りになっています。
と書かれています。
一応型の種類を別のもの(例えばlongやlong longとか)に変えてみればいいかなぁと思い、
試してみました。
[int] -> (i = 29) 辺りまでしか対応していない模様 [long] -> 同上 [long long] -> (i = 61) 辺りまでしか対応していない模様 (だいぶマシになった方...) [double] -> (i = 18) まではいいが、(i = 19) 辺りからは 1.04858e+06 のような数値になる [long double] -> 同上
思いつく型すべて試してみました。(charとかは別...)
それでもだいぶマシなものでも (2の64乗) の計算では i = 61 までしか表現できそうにもありません...
やはり自分でクラスなりを作るべきでしょうか。
コンパイル時は C++11 としてやっています。
(多分、C++17として使おうと思えばできるだろうけど...)
Cpprefference.com のオフライン版でチェックしてみましたが、
一番近そうなものがauto, std::any, std::varriant ぐらいでした...
(流石にautoはあり得ないし、std::anyは(加算とかで)加工して使うには
別の型(longとか)に変換しないといけないようだし..
追記:
調べてみると(unsigned long long int)と言う型を見つけたので
試してみました。
すると i = 63 で 0 に戻っていました。(= オーバーフローを起こしている)
追記:
できれば外部ライブラリに頼ることなく、(xのn乗) を表現できたらなぁ...と思っているのですが...
[追記2]
皆様、ご回答ありがとうございます。
どの回答をBAにするか悩みましたが、Amazing_GraceさんのをBAとさせて頂きます。
(できれば他の方々にもBAにしたいのですが...)
ちょっと今回の問題は私にはハードルが高かったかもしれません。(回答を読むと、私の苦手な範囲が使われていたりして...)
もうちょっと調べてから再挑戦することにします。
ありがとうございました。
回答4件
0
できれば外部ライブラリに頼ることなく、x^n を表現できたらなぁ...と思っているのですが...
ライブラリに相当するものを自分で書く必要があります。
データを保管するだけならint[]に入れておけばいいのですが、計算・表示には何かしらのコードの実装が必要となります。
そもそも論として、std::vectorやstd::stringの添字の型はvector::size_typeのようになっていますが、これは通常の整数型です。これを超える値にはみ出す心配は、もとよりありません（逆に、それだけ馬鹿でかいものは扱えません）。
投稿2020/01/13 05:06
編集2020/01/13 05:07総合スコア145183
ありがとうございます。
なるほど...
x64のCPU自体が、2020年時点では48ビット分のアドレス空間しかありませんので（アドレスのデータ幅は64ビットあるけど、うち16ビットは決まったルールで埋めることになっている）、最低64ビットあるlong longがあればじゅうぶん事足ります。
0
ベストアンサー
簡単な解決方法
自分も同様な計算をする時がありますが、そのときはめんどくさいのでpythonを使用して書いてます。
高速性を捨てる代わりに分かりやすく簡単に実行出来るのでおススメです。
C++で実行したい場合
十進数で表現することを諦めます。
個人的にはwhile文と二進数表現でのループ判定条件を試します。
二進数における桁上がりのプログラムを書くことと半的条件を記述することにより、桁数の心配をしなくて済むと思います。
実際のコード
以下のコードを活用することで2の64乗までは回すことが出来るはず
以下は、2の5乗回だが手直しを加えれば可能
注意点は、二進数の文字表記しか出来ないので、十進数の数値に変換する場合は別途コードを書く必要がある。
C++
1#include<iostream> 2#include<string> 3using namespace std; 4 5string binary_increment_function(string s){ 6 7 for(int i = 4; i >= 0; i--){ 8 9 if(s.at(i) == '1'){ 10 s.at(i) = '0'; 11 } 12 else{ 13 s.at(i) = '1'; 14 break; 15 } 16 17 } 18 19 return s; 20} 21 22int main() 23{ 24 string s = "00000"; 25 26 while(s != "10000"){ 27 28 s = binary_increment_function(s); 29 30 cout<<s<<endl; 31 } 32 33 return 0; 34}
投稿2020/01/13 05:01
編集2020/01/13 07:24
退会済みユーザー
総合スコア0
ありがとうございます。
やっぱりPython系ですか...
あと、私はあまり数学(というか数字自体)が得意ではないんですが、
>> 個人的にはwhile文と二進数表現でのループ判定条件を試します。
っていうのは何か名称がありますでしょうか。
例えば「多バイト列」とか(あくまで例)です。
キーワードが分かればもうちょっと調べられそうですが...
ごめんなさい。
名称とかはなく、考え方を述べさせて頂きました。
"C++ 二進数 計算（足し算）"
などで出てくるかもです。
しかし、二進数の場合は文字列なので自分でプログラムを書かなければいけないと思います。
コードを追加しました。
あなたの回答
tips
プレビュー
