0

ブール値のベクトルがストレージを 1 ビットに凝縮するという事実を利用しようとしています。次のレシピは、int 配列に繰り返しが含まれているかどうかを判断するための良い方法です (それとも、私の考え全体に本質的な欠陥があるのでしょうか?)。私のコンパイラである XCode がなぜこれを好まないのかわかりません

INT_MAX - INT_MIN + 1

次のコードの行。式を long にキャストしようとしましたが、同じ警告が表示されました。どんな助けでも大歓迎です！

bool contains_repeats_3(const std::vector<int>& V) { 
    std::vector<bool> bv (INT_MAX - INT_MIN + 1, 0); // <------ That's the problem line
    for (std::vector<int>::const_iterator it = V.begin() ; it != V.end(); ++it) {
        if (bv[*it - INT_MIN] == 1) {
            return true;
        } else { 
            bv[*it - INT_MIN] == 1;
        }
    }
   return false;    
}
4

2 に答える 2

3

まず、キャストする必要があるのは式ではなく、 のように個々のオペランド(long) INT_MAX - (long) INT_MIN + 1です。最初のものだけをキャストするだけで十分です。

第 2 に、 のlong範囲がプラットフォームの の範囲と同じである可能性は十分intにあります。つまり、 にキャストしてlongもオーバーフローを防ぐことはできません。にキャストする必要があるかもしれませんがlong long、利用できると仮定します。

第三に、そのサイズのベクトルが本当に必要ですか? std::vector<bool>あなたのプラットフォームにビットベクトルとして実装されることを願っています。または、少なくともプラットフォームが 64 ビットであること。32 ビット プラットフォームでは、配列サイズの限界を押し上げています。std::vectorこの種の容量を保証するものではないことに注意してください。bv.max_size()ベクターがそれだけ多くの要素を保持できるかどうかを確認することを期待したいかもしれません。

于 2013-11-08T06:46:51.193 に答える
2

基本的に、問題は INT_MAX が正で INT_MIN が負であることです。そのため、MAX から MIN を引くと、実際には加算されます。

10 - -2 = 10 + 2 = 12

次に、追加する数値はすでに int が格納できる最大の数値ですが、追加する数値は可能な最大の負の値です。INT_MAX と 0 の差は INT_MAX であるため、INT_MAX と何か <0 の差は INT_MAX より大きくなります。

(INT_MAX + 1) > INT_MAX
(INT_MAX - -1) > INT_MAX

基本的に、INT_MAX + any>0 は、int にあるよりも多くのビットを記述する必要があります。これはオーバーフローであり、「キャリー 1」と言うプログラミング方法です (キャリーに注釈を付けるビットは 1 つしかないため、複数になる可能性があります)。

b00 (0)、b01 (+1)、b10 (-2)、b11 (-1) の 4 つの可能なビットの組み合わせで、符号付き数値を表す 2 ビットがあるとします。

b11 - b01 = b10 および b00 - b01 = b11+sign であるため、b11 に -1 を割り当てます。

結果的に：

TINYINT_MAX = 1  (b01)
TINYINT_MIN = -2 (b10)

式がどのように機能するかは次のとおりです。

(TINYINT_MAX - TINYINT_MIN +  1 )
 b01           b10           b01
( 1 - -2  +  1 )
 b01  b10   b01

( 1  +  2  +  1 ) <-- things go pear shaped here.
 b01   xxx   b01

( 3  +  1 )
 xxx   b01

= 4

符号なしの場合は "3" を処理できますが、4 (b100) では必要なビット数が多くなります。

しかし、私たちの数値システムは +1、0、-1、-2 しかサポートしていないので、「-TINYINT_MIN」と言ったときに壊れてしまいました。

于 2013-11-08T07:15:01.650 に答える