C / C ++での16進数、2進数、および10進数間の効率的な変換
質問
正の整数のベース表現は3つあります:
- 10進、符号なしlong変数(例: unsigned long int NumDec = 200 )。
- 文字列変数の16進数(例: string NumHex =" C8" )
- バイナリ、文字列変数(例: string NumBin =" 11001000" )
3つの表現すべての数値を最も効率的な方法で変換できるようにしたい。つまり次の6つの関数を実装します。
unsigned long int Binary2Dec(const string & Bin) {}
unsigned long int Hex2Dec(const string & Hex) {}
string Dec2Hex(unsigned long int Dec) {}
string Binary2Hex(const string & Bin) {}
string Dec2Binary(unsigned long int Dec) {}
string Hex2Binary(const string & Hex) {}
それぞれに対して最も効率的なアプローチは何ですか? CとC ++を使用できますが、ブーストはできません。
編集:「効率」で;時間効率:最短の実行時間。
解決
他の人が指摘したように、 sscanf( )
、 printf()
および/または strtoul()
。ほとんどのアプリケーションで十分に高速であり、バグが発生する可能性は低くなります。ただし、これらの関数は、数値が任意のベースなどで表される非ASCII文字セットを処理する必要があるため、予想よりも汎用性が高いと言えます。一部のドメインでは、ライブラリ関数に勝つことができます。
したがって、最初に測定し、これらの変換のパフォーマンスが実際に問題である場合は、
1)一部のアプリケーション/ドメインでは、特定の数字、たとえば0、100、200、19.95が非常に頻繁に表示されるため、関数を最適化してそのような数字を大量のif()ステートメントで変換するのが理にかなっている場合があります、そして汎用ライブラリ関数にフォールバックします。 2)最も一般的な100の数値の場合はテーブルルックアップを使用し、ライブラリ関数にフォールバックします。大きなテーブルはキャッシュに収まらず、共有ライブラリに複数のインダイレクションが必要になる場合があるため、パフォーマンスを低下させないようにこれらを慎重に測定してください。
ブーストlexical_cast関数も見たいかもしれませんが、私の経験では後者は古き良きC関数と比較されています。
多くの人が言っていますが、何度も繰り返す価値があります。問題があることを示す証拠が得られるまで、これらの変換を最適化しないでください。最適化を行う場合は、新しい実装を測定してより高速であることを確認し、バグが発生するため、独自のバージョンのユニットテストが大量にあることを確認してください:-(
他のヒント
また、実装方法に興味がある場合は、ソースコードをご覧ください。 glibc、GNU Cライブラリ。
なぜこれらのルーチンは非常に時間効率が良くなければならないのですか?そのような主張はいつも私を不思議に思う。 strtol()のような明らかな変換メソッドは遅すぎるのでしょうか、それとももっと良くできるのでしょうか?通常、システム関数は非常に効率的です。一般性とエラーチェックのサポートが遅い場合がありますが、エラーの処理方法を検討する必要があります。 bin
引数に「0」と「1」以外の文字が含まれている場合、どうなりますか?アボート?大規模なエラーを伝播しますか?
「Dec」を使用する理由内部表現を表現するには?文字列表現を参照するには、12月、16進数、およびビンを使用する必要があります。 unsigned long
については10進数はありません。 10進数で数字を示す文字列を扱っていますか?そうでなければ、あなたはここの人々を混乱させており、さらに多くを混乱させようとしています。
バイナリと16進のテキスト形式間の変換は、ルックアップテーブルを使用して迅速かつ効率的に実行できますが、10進のテキスト形式を含むものはより複雑になります。
宿題の問題のように聞こえますが、一体何なのでしょうか...
簡単な答えは、2つのルックアップテーブルを使用してlong intから文字列に変換することです。各テーブルには256エントリが必要です。バイトを16進文字列にマッピングします:0-> " 00&quot ;, 1-> " 01"など。もう1つはバイトをビット文字列にマッピングします:0-> 「00000000」、1-> " 00000001"。
次に、long intの各バイトについて、正しい文字列を検索し、それらを連結するだけです。
文字列から長整数に戻すには、各文字の数値に適切な16または2の累乗を掛けて結果を合計することにより、16進数文字列とビット文字列を10進数に戻すことができます。
編集:バイナリ検索を実行して適切な文字列を見つけることにより、同じルックアップテーブルを逆変換に使用することもできます。これには、文字列のlog(256)= 8回の比較が必要です。残念ながら、文字列の比較が整数の乗算と加算よりもはるかに高速であるかどうかを分析する時間はありません。
タスクの半分について少し考えてみましょう-文字列化された基数nから符号なしlongに変換します。nは2の累乗です(2進数では2、16進数では16)。
入力が正しければ、この作業は比較、サブラクト、シフト、桁ごとに過ぎません。あなたの入力が正気でない場合、まあ、それはitいところですよね?変換を超高速で行うことは難しくありません。あらゆる状況下でうまくやることが課題です。
だから、あなたの入力が正気だと仮定しましょう、そしてあなたの変換の核心はこれです:
unsigned long PowerOfTwoFromString(char *input, int shift)
{
unsigned long val = 0;
char upperLimit = 'a' + (1 << shift)
while (*input) {
char c = tolower(*input++);
unsigned long digit = (c > 'a' && c < upperLimit) ? c - 'a' + 10 : c - '0';
val = (val << shift) | digit;
}
return val;
}
#define UlongFromBinaryString(str) PowerOfTwoFromString(str, 1)
#define UlongFromHexString(str) PowerOfTwoFromString(str, 4)
それがどれほど簡単かわかりますか?そして、それは正気でない入力では失敗します。作業の大部分は、パフォーマンスではなく入力の健全化に費やされます。
現在、このコードは2シフトのパワーを利用しています。ベース4、ベース8、ベース32などに拡張するのは簡単です。2のべき乗以外のベースでは機能しません。それらのために、あなたの数学は変えなければなりません。取得
val = (val * base) + digit
これは、この一連の操作でも概念的には同じです。基数による乗算は、シフトと同等になります。そのため、代わりに完全に一般的なルーチンを使用する可能性が高くなります。入力をサニタイズしながら、コードをサニタイズします。そして、その時点で、strtoulはおそらくあなたの最善策です。 バージョンへのリンクですa> strtoul。ほぼすべての作業は、エッジ条件の処理です。これは、エネルギーを集中すべき場所、つまり、正確で回復力のあるコードを知る手がかりになります。ビットシフトを使用した場合の節約は、たとえば、不適切な入力でクラッシュしない場合の節約に比べて最小限になります。
マクロを使用して、形式を入力として使用するだけではありません。少なくともCを使用している場合。
#define TO_STRING( string, format, data) \
sprintf( string, "##format##", data)
// Int
TO_STRING(buf,%d,i);
// Hex ( Two char representation )
TO_STRING(buf,%02x,i);
// Binary
TO_STRING(buf,%b,i);
またはsprintfを直接使用できます:または、複数のマクロを使用できます。
#define INT_STRING( buf, data) \
sprintf( buf, "%d", data)
#define HEX_STRING( buf, data) \
sprintf( buf, "%x", data)
#define BIN_TO_STRING( buf, data) \
sprintf( buf, "%b", data)
BIN_TO_STRING( loc_buf, my_bin );