0

いくつかの C++ 関数を .NET の BigInteger に移植することで、ビット シフトを独自に研究しています。BigInteger をシフトすると、空白が 1 で埋められていることに気付きました。

これは、負の数が 2 の補数形式で格納されていることに関係していると思います。

BigInteger num = -126;
compactBitsRepresentation = (uint)(int)(num << 16);

シフト後に何が起こったかを次に示します（最上位ビットが最初）

10000010 will be shifted 16
11111111100000100000000000000000 was shifted 16

同様のビットシフト操作がこのように動作することを常に期待する必要がありますか? これは、OpenSSL などの「bigNumber」のさまざまな言語や実装と一致していますか?

4

3 に答える 3

1

同様のビットシフト操作がこのように動作することを常に期待する必要がありますか?

問題の数値形式が負の数を表すために 2 の補数を使用している場合は、そうする必要があります (多くの場合はそうです)。数値の 2 の補数を形成するには、すべてのビットを反転して 1 を追加します。たとえば、次のようになります。

23 is represented as 00010111
-23 is represented as 11101001 (that is, 11101000 + 1)

さらに、型をより大きな型に変換すると、値は通常符号拡張されます。つまり、左端のビットがより大きな型の余分なビットに拡張されます。これにより、数値の符号が保持されます。

そうです、数値表現が数値に対して 1 で「埋められる」ことは非常に一般的です。

于 2013-03-11T00:45:17.480 に答える
1

BigInteger.LeftShiftオペレータードキュメントから：

整数プリミティブを使用したビット単位の左シフト演算とは異なり、LeftShift メソッドは元の BigInteger 値の符号を保持します。

したがって、.NET は、表示される動作を保証します。

私は bignum ライブラリにはあまり詳しくありませんが、OpenSSL の BIGNUM BN_lshift()` 関数のドキュメントには次のように書かれています。

BN_lshift()a を n ビット左にシフトし、結果を r に格納します ("r=a*2^n")。BN_lshift1()a を 1 つ左にシフトし、結果を r に入れます ("r=2*a")。

演算は 2 の累乗による乗算で定義されるため、結果の BIGNUM を 2 の補数に変換すると (BIGNUM が内部でどのように数値を表すかわかりません)、.NET と同様の動作が見られます。

他の bignum ライブラリが同様に動作しても驚かないでしょうが、動作に依存したい場合はドキュメントを確認する必要があります。ただし、シフトは 2 の累乗による乗算または除算に非常に似ているため、シフトの代わりに適切な乗算または除算を使用することで、おそらく「移植可能な」動作を得ることができます。次に、確実にする必要があるのは、2 の補数表現への変換を取得できることだけです (これは、シフト操作の動作とはまったく関係のない問題です)。

于 2013-03-11T00:07:08.943 に答える
0

10000010 は最初に大きな幅に変更されます。この場合、4 バイト:

10000010 --> 11111111 11111111 11111111 10000010

数値が負であるため、左側に 1 が表示されます。

左シフトは単純に右から 0 を挿入し、左からビットをスローします。

11111111 11111111 11111111 10000010 << 16 -->
11111111 10000010 00000000 00000000
于 2013-03-11T00:00:22.450 に答える