9

この関連する質問は、コンパイル時に符号付き型の最大値を決定することに関するものです。

C の質問: off_t (およびその他の符号付き整数型) の最小値と最大値

しかし、実行時time_tに符号付き型 ( or などoff_t)の最大値を決定するのは非常に難しい作業のように思われることに気付きました。

私が考えることができる解決策に最も近いものは次のとおりです。

uintmax_t x = (uintmax_t)1<<CHAR_BIT*sizeof(type)-2;
while ((type)x<=0) x>>=1;

typeこれにより、パディング ビットがない限りループが回避されますが、パディング ビットがある場合type、キャストは実装定義の動作を呼び出します。これは、シグナルまたは無意味な実装定義の変換 (符号ビットの削除など) である可能性があります。

私の意見では、この問題は解決できないと考え始めています。これは少し不安であり、C 標準の欠陥であると考えています。私が間違っていることを証明するためのアイデアはありますか?

4

12 に答える 12

4

まず、C で「整数型」がどのように定義されているかを見てみましょう。ISO/IEC 9899、§6.2.6.2 から引用:

6.2.6.2 整数型
1
unsigned char 以外の符号なし整数型の場合、オブジェクト表現のビットは、値ビットとパディング ビットの 2 つのグループに分けられます (後者のいずれかが存在する必要はありません)。N 値ビットがある場合、各ビットは 1 から 2N-1 までの異なる 2 の累乗を表すため、そのタイプのオブジェクトは純粋なバイナリ表現を使用して 0 から 2N-1 までの値を表すことができます。これは、値表現として知られるものとします。パディングビットの値は規定されていない.44)
2
符号付き整数型の場合、オブジェクト表現のビットは、値ビット、パディング ビット、符号ビットの 3 つのグループに分けられます。パディング ビットは必要ありません。正確に 1 つの符号ビットがあります。値ビットである各ビットは、対応する符号なし型のオブジェクト表現の同じビットと同じ値を持つものとします (符号付き型に M 個の値ビットがあり、符号なし型に N 個の値ビットがある場合、M ≤ N)。符号ビットがゼロの場合、結果の値には影響しません。符号ビットが 1 の場合、値は次のいずれかの方法で変更されます。

— 符号ビット 0 の対応する値は否定されます (符号と大きさ)。
— 符号ビットの値は -(2N) (2 の補数) です。
— 符号ビットの値は -(2N − 1) (1 の補数) です。

これらのどれが適用されるかは実装定義であり、符号ビットが 1 ですべての値のビットがゼロ (最初の 2 つの場合) の値、または符号ビットとすべての値のビットが 1 (1 の補数の場合) の値がトラップ表現であるかどうかと同様です。または正常値。符号と大きさと 1 の補数の場合、この表現が正常な値であれば、負のゼロと呼ばれます。

したがって、次のように結論付けることができます。

  • ~(int)0トラップ表現の可能性があります。つまり、すべてのビットを に設定するのは悪い考えです
  • int値に影響を与えないパディング ビットが にある可能性があります
  • 実際に 2 の累乗を表すビットの順序は定義されていません。符号ビットが存在する場合は、符号ビットの位置も同様です。

良いニュースは次のとおりです。

  • 符号ビットは 1 つだけです
  • 値 1 を表すビットは 1 つだけです。


それを念頭に置いて、 の最大値を見つける簡単なテクニックがありますint。符号ビットを見つけて 0 に設定し、他のすべてのビットを 1 に設定します。

符号ビットを見つけるにはどうすればよいでしょうか。を考慮int n = 1;してください。これは厳密に正であり、1 ビットとおそらく一部のパディング ビットのみが 1 に設定されていることが保証されています。次に、他のすべてのビットについて、真でiあればi==01 に設定し、結果の値が負かどうかを確認します。そうでない場合は、0 に戻します。そうでない場合は、符号ビットが見つかりました。

符号ビットの位置がわかったので、 を取りint n、符号ビットをゼロに設定し、他のすべてのビットを 1 に設定すると、tadaa、可能な最大int値が得られます。

int 最小値を決定することは、もう少し複雑で、読者の演習として残されています。



intC 標準では、2 つの異なる が同じように動作する 必要はないことに注意してください。私が間違っていなければ、intたとえばそれぞれの符号ビットが異なる位置にある 2 つの異なるオブジェクトが存在する可能性があります。



編集:このアプローチについて R.. (以下のコメントを参照) と話し合っているうちに、いくつかの点で欠陥があり、より一般的には解決策がまったくないと確信するようになりました。この投稿を修正する方法 (削除する以外) が見当たらないので、以下のコメントが意味をなすようにそのままにしておきます。

于 2011-04-21T13:19:31.727 に答える
3

数学的には、サイズ n (na 正の整数) の有限集合 (X、および比較演算子 (X の x、y、z; x<=y および y<=z は x<=z を意味する)) がある場合、それは最大値を見つけるための非常に単純な問題. (また、存在します.)

この問題を解決する最も簡単な方法ですが、最も計算コストがかかるのは、すべての可能な値を含む配列を生成してから、最大値を見つけることです。

パート 1. 有限メンバー セットを持つ型には、その型の特定のメンバーを一意に表すために使用できる有限数のビット (m) があります。考えられるすべてのビット パターンを含む配列を作成するだけです。ここで、特定のビット パターンは特定の型の特定の値で表されます。

パート 2. 次に、各 2 進数を指定された型に変換する必要があります。このタスクは、プログラミングの経験がないため、これがどのように達成されるかについて話すことができない場所です。キャスティングについていくつか読んだことがありますが、それでうまくいくでしょうか？それとも他の変換方法ですか？

パート 3. 前のステップが完了したと仮定すると、目的の型の値の有限セットと、そのセットに対する比較演算子が得られます。最大を見つけます。

しかし、もし...

...指定されたタイプのメンバーの正確な数がわからない? 過大評価よりも。妥当な過大評価ができない場合は、その数に物理的な限界があるはずです。過大な見積もりが得られたら、考えられるすべてのビット パターンをチェックして、どのビット パターンがその型のメンバーを表しているかを確認します。使用されていないものを破棄した後、指定された型のメンバーを表すすべての可能なビット パターンのセットができました。この最近生成されたセットは、パート 1 で使用するものです。

...その型には比較演算子がありませんか? 特定の問題は不可能であるだけでなく、論理的に無関係です。つまり、指定された型の 2 つの値を比較する場合に意味のある結果を与えるアクセス権がプログラムにない場合、指定された型はプログラムのコンテキストで順序付けされません。順序付けがなければ、最大値などありません。

...与えられた 2 進数を与えられた型に変換することはできませんか? その後、メソッドは壊れます。ただし、前の例外と同様に、型を変換できない場合、ツールセットは論理的に非常に制限されているように見えます。

技術的には、バイナリ表現と特定の型の間で変換する必要がない場合があります。変換の全体的なポイントは、生成されたリストが網羅的であることを保証することです。

...問題を最適化したいですか? 指定された型が 2 進数からどのようにマップされるかについての情報が必要です。たとえば、unsigned int、signed int (2 の補数)、signed int (1 の補数) は、それぞれ文書化された簡単な方法でビットから数値にマップされます。したがって、unsigned int の可能な最大値が必要で、m ビットで作業していることがわかっている場合は、単純に各ビットを 1 で埋め、ビット パターンを 10 進数に変換してから数値を出力できます。

これは最適化に関連しています。なぜなら、このソリューションの最もコストのかかる部分は、考えられるすべての答えをリストすることだからです。与えられた型がビットパターンからどのようにマッピングされるかについての事前の知識があれば、代わりにすべての潜在的な候補を作成することにより、すべての可能性のサブセットを生成できます。

幸運を。

于 2011-04-27T00:55:22.513 に答える
3

更新:ありがたいことに、以下の以前の回答は間違っていました。この質問には解決策があるようです。

intmax_t x;
for (x=INTMAX_MAX; (T)x!=x; x/=2);

このプログラムはx、 type の可能な最大値を含む結果をT生成するか、実装定義のシグナルを生成します。

シグナルケースを回避することは可能かもしれませんが、困難で計算上実行不可能です (考えられるすべてのシグナル番号に対してシグナルハンドラーをインストールする必要がある場合など)。したがって、この答えは完全に満足できるものではないと思います。POSIX シグナル セマンティクスは、それを実行可能にするのに十分な追加プロパティを提供する場合があります。わからない。

興味深い部分は、特に、シグナルを生成する実装を使用していないと安心できる場合は(T)x、実装定義の変換が発生したときに何が起こるかです。上記のループのトリックは、変換のための実装の値の選択にまったく依存しないことです。依存するのは、 type に適合する(T)x==x場合にのみ可能なことです。そうでない場合、 の値はtypeの任意の式の可能な値の範囲外になるためです。xTxT

(T)x==x上記のプロパティを考慮していないため、古い考えです。

私が探していることが不可能であるという証明のスケッチがあると思います:

  1. X を適合する C 実装とし、 と仮定しINT_MAX>32767ます。
  2. X と同一の新しい C 実装 Y を定義しますが、INT_MAXとの値INT_MINはそれぞれ 2 で除算されます。
  3. Y が適合する C 実装であることを証明します。

このアウトラインの本質的な考え方は、符号付きの型を持つ範囲外の値に関連するすべてが実装定義または未定義の動作であるという事実により、符号付き整数型の上位値ビットの任意の数を考慮することができるということです。の制限マクロを除いて、実際に実装に変更を加えることなく、パディング ビットとしてlimits.h。

これが正しいか偽物に聞こえるかについて何か考えはありますか? それが正しければ、賞金をより厳格にするために最善を尽くすことができる人に喜んで賞金を授与します.

于 2011-04-23T00:58:50.643 に答える
1

私はCに比較的慣れていないので、ここでばかげたことを書いているだけかもしれませんが、これはaの最大値を取得するために機能しませんsignedか?

unsigned x = ~0;
signed y=x/2;

これはばかげた方法かもしれませんが、私が見た限り、unsigned max値はsigned max*2+1 です。逆に効かないの？

これが完全に不適切で不正確であることが判明した場合は、時間を無駄にして申し訳ありません。

于 2012-06-12T21:22:33.577 に答える
0

なぜこれが問題になるのでしょうか? 型のサイズはコンパイル時に固定されるため、型の実行時のサイズを決定する問題は、型のコンパイル時のサイズを決定する問題に変わります。任意のターゲット プラットフォームに対して、 のような宣言は、off_t offset固定サイズを使用するようにコンパイルされ、結果の実行可能ファイルをターゲット プラットフォームで実行するときに常にそのサイズが使用されます。

ETA:で型のサイズを取得できtypeますsizeof(type)。次に、一般的な整数サイズと比較して、対応するMAX/MINプリプロセッサ定義を使用できます。次のように使用する方が簡単な場合があります。

uintmax_t bitWidth = sizeof(type) * CHAR_BIT;
intmax_t big2 = 2;  /* so we do math using this integer size */
intmax_t sizeMax = big2^bitWidth - 1;
intmax_t sizeMin = -(big2^bitWidth - 1);

値が基礎となる「物理」型によって表現可能であるからといって、その値が「論理」型の値に対して有効であるとは限りません。max 定数と min 定数が提供されていない理由は、これらが「半不透明」なタイプであり、その使用が特定のドメインに制限されているためだと思います。不透明度が低いことが望ましい場合、必要な情報を取得する方法が見つかることがよくあります。たとえば、 の説明でoff_tSUSv2 によって言及されている、 の大きさを把握するために使用できる定数などです。<unistd.h>

于 2011-04-20T22:27:23.177 に答える
0

パディング ビットを変更してもトラップ表現が作成されないと仮定すると、 を使用しunsigned char *てループ オーバーし、符号ビットに到達するまで個々のビットを反転できます。初期値が だった場合~(type)0、これにより最大値が得られます。

type value = ~(type)0;
assert(value < 0);

unsigned char *bytes = (void *)&value;
size_t i = 0;
for(; i < sizeof value * CHAR_BIT; ++i)
{
    bytes[i / CHAR_BIT] ^= 1 << (i % CHAR_BIT);
    if(value > 0) break;
    bytes[i / CHAR_BIT] ^= 1 << (i % CHAR_BIT);
}

assert(value != ~(type)0);
// value == TYPE_MAX
于 2011-01-27T09:49:31.403 に答える
0

これを実行時に許可するため、事実上の反復左シフトを行う関数を作成できます(type)3。値が を下回った時点で停止する0と、トラップ表現が得られません。そして反復回数 - 1 は符号ビットの位置を教えてくれます。

左シフトの問題が残ります。演算子を使用するだけで<<はオーバーフローが発生するため、これは未定義の動作になるため、演算子を直接使用することはできません。

これに対する最も簡単な解決策は、上記のようにシフト3された a を使用するのではなく、ビット位置を反復処理し、常に最下位ビットも追加することです。

type x;
unsigned char*B = &x;
size_t signbit = 7;
for(;;++signbit) {
  size_t bpos = signbit / CHAR_BIT;
  size_t apos = signbit % CHAR_BIT;
  x = 1;
  B[bpos] |= (1 << apos);
  if (x < 0) break;
}

(開始値7は、符号付き型が持つ必要がある最小幅だと思います)。

于 2011-01-27T17:35:56.313 に答える
0

次の疑似コードのようなものが仕事をするべきではありませんか?

signed_type_of_max_size test_values =
    [(1<<7)-1, (1<<15)-1, (1<<31)-1, (1<<63)-1];

for test_value in test_values:
    signed_foo_t a = test_value;
    signed_foo_t b = a + 1;
    if (b < a):
        print "Max positive value of signed_foo_t is ", a

またはもっと単純に、なぜ次のように動作しないのでしょうか?

signed_foo_t signed_foo_max = (1<<(sizeof(signed_foo_t)*8-1))-1;

ただし、私自身のコードでは、プリプロセッサ マクロを定義するビルド時のチェックを行うことは間違いありません。

于 2011-01-27T05:42:07.523 に答える
-3

「どうやって？」と質問する前に 、まず「なぜ？」という質問をする必要があります。. 実行時にそれを知る必要があるのはなぜですか? これは実際の問題に関連していますか、それとも単に学術的な問題ですか?

コンパイル時にそれを決定する必要はまったくありません。プログラマーが特定のニーズを満たすプログラムを作成している場合、そのプログラムが実行される環境についてある程度の知識を持っていることは間違いありません。

于 2011-04-26T12:52:57.293 に答える