私は C++ を学習している初心者 (自己学習型) プログラマーです。最近、演習として 2 進化 10 進数 (BCD) クラスを実装することにしたので、Project Eulerで非常に大きな数を処理できるようになりました。なるべく基本的に、ちゃんと一からやりたいと思います。
入力数値のすべての桁が個別の int として保存される int の配列の使用から始めました。各 BCD 桁は 4 ビットのみでエンコードできることを知っているので、これに int 全体を使用するのは少しやり過ぎだと思いました。現在、bitset<4> の配列を使用しています。
編集:これの主な理由は演習です-全体のポイントはクラスを自分で作成することであるため、GMPのようなライブラリを使用したくありません。10 進数ごとに 4 ビットのみを使用することを確認する方法はありますか?
1 つだけ注意してください。 の配列を使用するbitset<4>と、long の配列と同じ量のスペースが必要になります。bitset は通常、ワードサイズの整数の配列をビットのバッキングストアにすることで実装されます。これにより、ビット単位の操作はバイト単位ではなくビット単位のワード操作を使用できるため、一度により多くの処理が行われます。
また、あなたの動機についても質問します。BCD は、通常、数字の文字列をシステム間で送信するときに、数字の文字列のパック表現として使用されます。通常、算数とは何の関係もありません。あなたが本当に欲しいのは、GMPのような任意のサイズの整数演算ライブラリです。
Greg Rogersが言ったように、ビットセットを使用しても、おそらくintよりもスペースを節約することはできず、他の利点も実際には提供されません。代わりにベクトルを使用するでしょう。必要なサイズの2倍ですが、各桁のインデックス作成がより簡単で高速になります。
パックされたBCDを使用する場合は、カスタムのインデックス関数を記述して、各バイトに2桁を格納できます。
- このやり過ぎのようなライブラリクラスも使用していますか?
- 詐欺だと思いますか？
- これを行うより良い方法はありますか？
1&2: そうでもない
3: 各バイトは 8 ビットなので、各 unsigned char に 2 つの BCD を格納できます。
このやり過ぎのようなライブラリクラスも使用していますか?
どちらのパフォーマンスが優れているかを確認するために、int の配列に対してベンチマークします。bitset<4> の配列の方が速い場合は、やり過ぎではありません。少しずつでも、体育の問題のいくつかに役立ちます
詐欺だと思いますか？
いいえ、まったくありません。
これを行うより良い方法はありますか？
Greg Rogers が示唆したように、独自のローリングから学びたいだけでない限り、任意精度ライブラリがおそらくより良い選択です。両方の方法 (ライブラリを使用する方法とライブラリを作成する方法) から学ぶべきことがあります。私は怠け者なので、普段は Python を使っています。
一般に、ビット操作は整数のコンテキストで適用されるため、パフォーマンスの観点からビット操作を行う本当の理由はありません。
経験を積むためにビットアプローチに行きたい場合は、これが役立つかもしれません
#include <stdio.h>
int main
(
void
)
{
typedef struct
{
unsigned int value:4;
} Nibble;
Nibble nibble;
for (nibble.value = 0; nibble.value < 20; nibble.value++)
{
printf("nibble.value is %d\n", nibble.value);
}
return 0;
}
問題の要点は、そのstruct内で、4 ビット幅の短い整数を作成していることです。内部的には、これは実際には整数ですが、意図した用途では、4 ビット整数のように見え、動作します。
これは、実際には無限ループであるforループによって明確に示されます。ニブル値が 16 に達すると、処理するビットが 4 ビットしかないため、値は実際にはゼロになります。その結果、nibble.value < 20は true になりません。
K&R ホワイト ブックを見ると、注意事項の 1 つに、このようなビット操作は移植可能ではないという事実があるため、プログラムを別のプラットフォームに移植したい場合は、動作する場合と動作しない場合があります。
楽しむ。
基数 10 表現 (つまり、配列の各セルの 10 進数) を取得しようとしています。この方法では、スペース (1 桁あたり 1 つの int) または時間 (1 桁あたり 4 ビットですが、パック/アンパックのオーバーヘッドがあります) が無駄になります。
たとえば、base-256 を試してみて、バイトの配列を使用してみませんか? または、整数の配列を使用した base-2^32 でさえありますか? 操作は base-10 と同じ方法で実装されます。異なるのは、数値を人間が読める文字列に変換することだけです。
次のように機能します: base-256 を想定すると、各「数字」には 256 の可能な値があるため、0 ～ 255 の数字はすべて 1 桁の値になります。256 は 1:0 として書かれます (「数字」を区切るためにコロンを使用します。基数 16 のように文字を使用することはできません)。基数 10 の類推は、9 の後に 10 がある方法です。 -10) = 4 * 256 + 6 = 4:6 (base-256)。また、1020 (base-10) = 3 * 256 + 252 = 3:252 (base-256) は、base-256 の 2 桁の数値です。
ここで、最下位桁が最初になるようにバイト配列に数字を入れると仮定しましょう。
unsigned short digits1[] = { 212, 121 }; // 121 * 256 + 212 = 31188
int len1 = 2;
unsigned short digits2[] = { 202, 20 }; // 20 * 256 + 202 = 5322
int len2 = 2;
次に、追加は次のようになります（警告：メモ帳のコードは壊れている可能性があります）：
unsigned short resultdigits[enough length] = { 0 };
int len = len1 > len2 ? len1 : len2; // max of the lengths
int carry = 0;
int i;
for (i = 0; i < len; i++) {
int leftdigit = i < len1 ? digits1[i] : 0;
int rightdigit = i < len2 ? digits2[i] : 0;
int sum = leftdigit + rightdigit + carry;
if (sum > 255) {
carry = 1;
sum -= 256;
} else {
carry = 0;
}
resultdigits[i] = sum;
}
if (carry > 0) {
resultdigits[i] = carry;
}
最初の反復では、次のようになります。
2 回目の繰り返しで:
したがって、最後の resultdigits[] = { 158, 142 }、つまり 142:158 (base-256) = 142 * 256 + 158 = 36510 (base-10) となり、正確には 31188 + 5322 になります。
この数値を人間が読める形式に変換することは、決して簡単な作業ではないことに注意してください。10 または 256 による乗算と除算が必要であり、適切な調査なしにサンプルとしてコードを提示することはできません。利点は、演算「加算」、「減算」、および「乗算」を非常に効率的に行うことができ、基数 10 との間の大量の変換が計算の最初と最後に 1 回だけ行われることです。
そうは言っても、個人的には、バイト配列で基数 10 を使用し、メモリの損失は気にしません。これには、上記の定数 255 と 256 をそれぞれ 9 と 10 に調整する必要があります。