2

URL クエリ文字列で 50 桁の 10 進数の整数 ID を使用している Web サイトに遭遇しましたが、これは少し過剰に思えます。

最小の 50 桁の 10 進数は1.0 x 10^49、別名:

1000000000
0000000000
0000000000
0000000000
0000000000
  1. バイナリ表現には何ビットが含まれますか?
  2. 符号なし 32 ビット整数または 64 ビット整数の範囲制限を考慮して、このような大きな 10 進数を 2 進数に変換するにはどうすればよいでしょうか?

私は純粋なプログラマーの好奇心からだけ質問します - これは大学の質問でも、仕事の問題でも、面接のパズルでもありません!

4

8 に答える 8

8

最小のバイナリ表現 (整数精度) は、数値の対数 (基数 2) を取得することによって見つけることができます。この場合、バイナリ ビットの最小量は log(10^49) = 162.77 になります。整数が必要なので、163 ビットと呼びます。

その数値を表現する必要があり、浮動小数点表現の精度が不十分な場合は、BigIntegerライブラリを使用するだけです。

于 2009-07-15T08:36:48.623 に答える
7

  1. 49 * log(10) / log(2) = 162.774477 なので、バイナリ表現には 163 ビットが含まれます。

  2. bigint クラスを使用し、10 進数から 2 進数への変換に標準アルゴリズムを適用します。

于 2009-07-15T08:37:52.130 に答える
4

すべての 10 進数はビットと同じ情報を伝えるためlb 10、50 桁の数値はすべてビットに収まりceil(lb(10)*50) = 167ます。

特に、10 進数から 2 進数への変換は、手作業でもそれほど難しくありません。2 で除算し、モジュラス (最後の桁が奇数の場合は 1、偶数の場合は 0) をバイナリ結果の最後に置きます。プログラムでそのような大きな数値が必要な場合は、プラットフォームの大きな整数の実装を使用してください。たとえばBigInteger、Java とintPython だけです。それがない場合は、数値ライブラリを探してください。

ああ、バイナリの 10^49 は 163 ビット長です。

110
1101 0111 1001 1111 1000 0010 0011 0010
1000 1110 1010 0011 1101 1010 0110 0001
1110 0000 0110 0110 1110 1011 1011 0010
1111 1000 1000 1010 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
于 2009-07-15T08:33:44.823 に答える
1

そのような数値を変換するために、適切な長整数操作ライブラリを使用できます。使用が許可されていない場合は、ソースを読むことで、そのようなことが効率的に行われる方法についての有用な知識を得ることができます。

方程式を解くために必要なビット数については、次のとおりです。

2 N = 10 50

両方の部分のログ2を取得します。

N = ログ2 10 50

log 2を log 10に変換します。

N = ログ2 10 50 = ログ10 10 50 /ログ10 2 = 50 / ログ10 2

N の次の整数 (ceil) を取得します。これが必要なビット数です。

于 2009-07-15T08:38:09.463 に答える
0

50 桁の 10 進整数の範囲は 10^49 から 10^50-1 です。10^49 は 163 ビット、10^50-1 は 167 ビットです。正確なビット数が必要な場合は、「近道」の 50*log 10 (2) を計算するのではなく、これらの大きな数値の対数を直接取得する必要があります。

別の方法として、任意精度の 10 進数 - 2 進数コンバーターを使用して数値を 2 進数に変換し、ビットをカウントすることもできます (ところで、私がリンクしたコンバーターがビットをカウントします)。

于 2009-07-15T12:27:10.080 に答える
0

1) 2^10 ~ 10^3 なので 10^48 ~ 2^160; 10^49 は 164 ビット量になります。

2) BigInteger または MPI クラスを使用します (言語標準 API ライブラリに含まれていない場合は、これらのクラスがたくさんあります)。Knuth に詳細があります。

于 2009-07-15T08:34:12.543 に答える
0

数値Xを格納するとは、正確にはどういう意味ですか?

  1. 0 から X までのすべての数値を格納するということですか?
  2. それとも -X と X の間のすべての数字ですか?
  3. または、情報のみを保存する: null / X.

私の直感では、インタビュアーは 3 番目のものを意味していたのかもしれません。答えは 1 ビットです。

于 2009-07-15T08:38:20.570 に答える
0

大きな整数を処理する高水準言語を使用します。irb (Ruby) セッションの例:

>> (10**49).to_s
=> "10000000000000000000000000000000000000000000000000"
>> (10**49).to_s(2)
=> "1101101011110011111100000100011001010001110101000111101101001100001111000000110011011101011101100101111100010001010000000000000000000000000000000000000000000000000"
>> (10**49).to_s(2).size
=> 163
于 2009-07-15T08:40:20.643 に答える