掲示板ランキング  水着  着ぐるみ・コスチューム  雨具


掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板1

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.6886

符号なし整数型と符号付き整数型の精度の関係
投稿者---yoh2(2006/12/07 21:57:19)


環境: C99処理系全般

別スレの質問(最小設定; http://www3.realint.com/cgi-bin/tarticles.cgi?pointc2+6879)
に関連していますが、あちらでやるとスレ乗っ取りになりそうなので、新規に立てました。

上記リンク先の質問について、C99の枠組のみ用いて実現できないかどうか考えるために
規格書(JIS X 3010:2003)を読んでいるうちに、ひとつ疑問が沸きました。
それは、符号なし整数型と符号付き整数型の精度(値ビットのビット数)の関係です。
これまで、暗黙のうちに 符号なしの精度+1 = 符号付整数の精度+1 だと思っていたの
ですが、規格書を読む限り、符号なしの精度 > 符号付整数の精度 という所までしか
規定されていないように思いました。

つまり、unsigned intの精度が64ビット、signed intの精度が31ビットという系が
あっても実はC99的にはOKなのではないかと。
この考えは合っているでしょうか?

現実問題として、そのような変態処理系はない(と思う)ですし、わざわざ作る理由も
ないため、単なる言葉遊びにしかならないわけですが、気になったので質問してみました。

ちなみに、符号なしの精度+1 = 符号付整数の精度+1 が保証されるなら、limits.hに
頼らず、絶対値+符号ビット/1の補数/2の補数すべてに同時に対応した、最小整数値を表す
マクロを作れそうです。
とはいえ、MIN(short)のように、欲しい型を引数に指定しなければなりませんが。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:符号なし整数型と符号付き整数型の精度の関係 6887 たかぎ 2006/12/07 23:09:52
<子記事> Re:符号なし整数型と符号付き整数型の精度の関係 6897 yoh2 2006/12/08 21:51:54


No.6887

Re:符号なし整数型と符号付き整数型の精度の関係
投稿者---たかぎ(2006/12/07 23:09:52)
http://takagi.in/


>これまで、暗黙のうちに 符号なしの精度+1 = 符号付整数の精度+1 だと思っていたの
>ですが、

符号なしの精度 = 符号付整数の精度+1 の間違いではないでしょうか?

>つまり、unsigned intの精度が64ビット、signed intの精度が31ビットという系が
>あっても実はC99的にはOKなのではないかと。
>この考えは合っているでしょうか?

たぶんそうです。
また、unsigned intの精度もsigned intの精度も31ビットの処理系があってもOKだと思います。
(つまり、unsigned intの最上位ビットは詰め物ビット)

>現実問題として、そのような変態処理系はない(と思う)ですし、わざわざ作る理由も
>ないため、単なる言葉遊びにしかならないわけですが、気になったので質問してみました。

世の中には特殊なプロセッサもあるので、何ともいえませんね。
DSPとか、スーパーコンピュータとか、変態的なアーキテクチャは結構ありますし...。

>ちなみに、符号なしの精度+1 = 符号付整数の精度+1 が保証されるなら、limits.hに
>頼らず、絶対値+符号ビット/1の補数/2の補数すべてに同時に対応した、最小整数値を表す
>マクロを作れそうです。
>とはいえ、MIN(short)のように、欲しい型を引数に指定しなければなりませんが。

符号なしの精度 = 符号付整数の精度+1 だとしても、たぶん無理だと思います。
特に、符号ビットにはみ出して左シフトすると未定義の動作になったり、表現できない値を符号付き整数型にキャストした場合の動作が処理系定義になったり、詰め物ビットや負数の内部表現やトラップ表現まで考えると、まず無理です。

具体的には、short型が16ビットの処理系で、SHRT_MINを求めようとしても、-32767が最小値なのか-32768が最小値なのか知るすべがありません。
仮に、負数の内部表現が2の補数であると分かった場合でも、0x8000というビットパターンがトラップ表現なのか、正しい値なのかを知るすべはありません。



この投稿にコメントする

削除パスワード

No.6890

Re:符号なし整数型と符号付き整数型の精度の関係
投稿者---yoh2(2006/12/08 02:05:51)


>>これまで、暗黙のうちに 符号なしの精度+1 = 符号付整数の精度+1 だと思っていたの
>>ですが、
>
>符号なしの精度 = 符号付整数の精度+1 の間違いではないでしょうか?

間違えました。ご指摘の通り、符号なしの精度 = 符号付整数の精度+1 の間違いです。

>>つまり、unsigned intの精度が64ビット、signed intの精度が31ビットという系が
>>あっても実はC99的にはOKなのではないかと。
>>この考えは合っているでしょうか?
>
>たぶんそうです。

うーん。そうなりますか。
私の仕様見落しだという線に掛けてたのですが。

>また、unsigned intの精度もsigned intの精度も31ビットの処理系があってもOKだと思います。
>(つまり、unsigned intの最上位ビットは詰め物ビット)

あ、確かに。

§6.2.5 型
| 符号付き整数型の負でない値の範囲は、対応する符号無し整数型の範囲の部分集合とし、
| 二つの型において同じ値の表現は同じとする。

「真」部分集合ではありませんからね。
符号なしの精度 >= 符号付整数の精度と、イコールが付きますね。

>>ちなみに、符号なしの精度+1 = 符号付整数の精度+1 が保証されるなら、limits.hに
>>頼らず、絶対値+符号ビット/1の補数/2の補数すべてに同時に対応した、最小整数値を表す
>>マクロを作れそうです。
>>とはいえ、MIN(short)のように、欲しい型を引数に指定しなければなりませんが。
>
>符号なしの精度 = 符号付整数の精度+1 だとしても、たぶん無理だと思います。
>特に、符号ビットにはみ出して左シフトすると未定義の動作になったり、表現できない値を符号付き整数型にキャストした場合の動作が処理系定義になったり、詰め物ビットや負数の内部表現やトラップ表現まで考えると、まず無理です。
>
>具体的には、short型が16ビットの処理系で、SHRT_MINを求めようとしても、-32767が最小値なのか-32768が最小値なのか知るすべがありません。
>仮に、負数の内部表現が2の補数であると分かった場合でも、0x8000というビットパターンがトラップ表現なのか、正しい値なのかを知るすべはありません。

確かに、符号なしの精度 = 符号付整数の精度+1 という保証だけでは無理そうです。
しかし、もうひとつ、最小値を表すマクロ MIN(T) の、Tの部分に指定できるパラメータを
short、int、long、long longに限る(*)とすれば、以下のように最小整数値を
表せるのではないかと思うのですがいかがでしょう?

(*) MIN(signed long) のように"signed"を付けたり、typedef int INT; として、
MIN(INT)とすることはできない、という意味。
"signed"と"unsigned"が付けられる型なら、__int64のような拡張整数型もOK。

まず、負数の表現にどの形式を使っているかの判定は以下のようにして行えます。

(((T)-1) & 3)

これが1なら絶対値+符号ビット ((signed T)-1の値ビット: 000...001)
2なら1の補数。((T)-1の値ビット: 111...110)
3なら2の補数。((T)-1の値ビット: 111...111)

絶対値+符号ビットの系と、1の補数系の場合、最小値は -最大値 だから以下のようになります。

-(T)(((unsigned T)-1) >> 1)

ここで、(unsigned T)-1の値はunsigned Tの最大値になります。(符号無し整数の
キャストの定義より、-1 + (unsigned Tの最大値+1)となるため)。
また、符号なしの精度 = 符号付整数の精度+1 という条件より、((unsigned T)-1) >> 1が
Tの最大値、つまりTで表現できる範囲。よってTに安全にキャストできます。

一方、2の補数系の場合、最小値は -最大値 - 1 となるので、
-(T)(((unsigned T)-1) >> 1) - 1
となります。

ここまでの計算で、詰め物ビットについて何も触れていませんでしたが、§6.2.6.2 整数型 の脚注44に

| 詰め物ビットの幾つかの組合わせが、トラップ表現を埋む可能性がある。
| (中略)それにもかかわらず、オーバーフローのように例外条件の一部となる場合を除き、
| 正しい値を用いる算術演算が、トラップ表現を生成することはない。

という記述があることと、未定義、処理系定義の結果を生まない演算のみ使っているので
トラップ表現については問題ないかと。

これらを組合わせて、最終的に、符号付き整数型Tの最小値を求めるマクロは

#define MIN(T) ((T)(-(T)(((unsigned T)-1) >> 1) - ((((T)-1) & 3) == 3)))

となります。

もっともも、仕様にそもそも 符号なしの精度 = 符号付整数の精度+1 の保証がない以上、
お遊びの域を出ませんが。


この投稿にコメントする

削除パスワード

No.6891

Re:符号なし整数型と符号付き整数型の精度の関係
投稿者---yoh2(2006/12/08 02:13:40)


ひとつ訂正。

>これが1なら絶対値+符号ビット ((signed T)-1の値ビット: 000...001)
>2なら1の補数。((T)-1の値ビット: 111...110)
>3なら2の補数。((T)-1の値ビット: 111...111)

最初の "((signed T)-1の値ビット: 000...001)" の "signed" に深い意味はありません。
ただの(T)にするか、(signed T)にするか迷って、何度か変更しているうちに整合性が
崩れてしまったまま投稿してしまいました。

そもそも(T)によるキャストはいりませんね。


この投稿にコメントする

削除パスワード

No.6892

Re:符号なし整数型と符号付き整数型の精度の関係
投稿者---たかぎ(2006/12/08 09:53:51)
http://takagi.in/


>しかし、もうひとつ、最小値を表すマクロ MIN(T) の、Tの部分に指定できるパラメータを
>short、int、long、long longに限る(*)とすれば、以下のように最小整数値を
>表せるのではないかと思うのですがいかがでしょう?

大体いい感じだと思います。
一点だけ気になったのは、

>一方、2の補数系の場合、最小値は -最大値 - 1 となるので、
>-(T)(((unsigned T)-1) >> 1) - 1
>となります。

この部分です。分かりやすいように、16ビットのshort型について考えてみます。

-(short)(((unsigned short)-1) >> 1) -1

となり、-0x7fff-1 となることを期待しているようです。
ところが、このビットパターンは、符号ビットが1で値ビットがすべて0であり、それがトラップ表現であるかどうかは処理系に依存します。(6.2.6.2 整数を参照)

また、(short型における)このビットパターンがトラップ表現であり、かつint型も16ビットの場合には、最後の減算がオーバーフローを生じます。
int型が17ビット以上あれば、オーバーフローにはなりませんが、short型に型変換された時点でトラップ表現を生じます。

> 未定義、処理系定義の結果を生まない演算のみ使っているので

言葉だけの問題ですが、符号付き整数型に対するビット演算の結果は処理系定義ですね。
今回は、処理系定義の動作によって、内部表現を判別しているわけですが...。

また、上で書いたように、オーバーフローを生じる場合は未定義にもなり得ます。



この投稿にコメントする

削除パスワード

No.6899

整数型の内部表現について(Re:符号なし整数型と符号付き整数型の精度の関係)
投稿者---yoh2(2006/12/08 22:45:13)


まずは、元の題名から話がずれてきましたので改名してみました。
さて、本題。

>ところが、このビットパターンは、符号ビットが1で値ビットがすべて0であり、それがトラップ表現であるかどうかは処理系に依存します。(6.2.6.2 整数を参照)

あちゃー。負の0にばかり気をとられてて、完全に見落としてました。
これがある限りどうしようもなさげですね。
もしかして、以前の

>仮に、負数の内部表現が2の補数であると分かった場合でも、0x8000というビットパターンがトラップ表現なのか、正しい値なのかを知るすべはありません。

というご指摘はこのことを指していたのでしょうか。
てっきり、0x8000と書いても、最上位ビットが符号ビットであるという保証はなく、
"8"で立てたビットが詰め物ビットの可能性もあるため、トラップ表現になる可能性が
ある、という意味だと解釈していました。


>> 未定義、処理系定義の結果を生まない演算のみ使っているので
>
>言葉だけの問題ですが、符号付き整数型に対するビット演算の結果は処理系定義ですね。

確かに。処理系定義でなければ負数の表現形式の判別が不能ですね。
未定義の結果と予測不能な処理系定義の結果を生まない、とでもするべきでした。

結局、私の方でも、C99の最低限の枠組(+精度のに関する保証)だけでは符号付き整数の
最小値を表現するのは無理だという結論に達しました。
これ以上仮定を付け加えても面白くないですし、この結論で納得することにします。
何度も詳しいレスをありがとうございました。

しかし、C99に関してはそれなりに詳しい(ISO/IEC 9899:1999を持っていないので
JIS X 3014:2003に限りますが)つもりでいたのですが、まだまだのようです。
うーん、奥が深い……

# 次期C規格でさらに選択肢が増えて、「値ビットの内部表現は純粋二進表現または
# グレイコードとする(処理系定義)」なんてことなったら泣くかも。


この投稿にコメントする

削除パスワード

No.6901

Re:整数型の内部表現について(Re:符号なし整数型と符号付き整数型の精度の関係)
投稿者---たかぎ(2006/12/08 23:38:20)
http://takagi.in/


>もしかして、以前の
>
>>仮に、負数の内部表現が2の補数であると分かった場合でも、0x8000というビットパターンがトラップ表現なのか、正しい値なのかを知るすべはありません。
>
>というご指摘はこのことを指していたのでしょうか。

はい。そのつもりでした。

>しかし、C99に関してはそれなりに詳しい(ISO/IEC 9899:1999を持っていないので
>JIS X 3014:2003に限りますが)つもりでいたのですが、まだまだのようです。

JIS X 3014:2003はC++の規格ですね。

># 次期C規格でさらに選択肢が増えて、「値ビットの内部表現は純粋二進表現または
># グレイコードとする(処理系定義)」なんてことなったら泣くかも。

機能拡張はあっても、既存機能の選択肢は狭くなる傾向にあるので、それは大丈夫だと思います。
でも、次期規格は、char16_t型やら_Fract型やら_Accum型などが増えそうなので、内部表現に関してはまた(別の意味で)ややこしくなりそうな予感がします。



この投稿にコメントする

削除パスワード

No.6902

Re:整数型の内部表現について(Re:符号なし整数型と符号付き整数型の精度の関係)
投稿者---yoh2(2006/12/10 00:18:47)


>JIS X 3014:2003はC++の規格ですね。

最後までこんなポカをやってしまうとは。恥ずかしい限りです。
ちなみに、C++の規格書の方にも一通り目を通してはいるのですが、ネームスペースの絡んだ
名前解決やらオーバーロードの解決やらテンプレート関数の型の推定やらややこしい規格が多すぎて、
今回の例のように規格の重箱の隅をつついて遊んでみることができる状態ではありせん。
こちらも精進あるのみ……

>># 次期C規格でさらに選択肢が増えて、「値ビットの内部表現は純粋二進表現または
>># グレイコードとする(処理系定義)」なんてことなったら泣くかも。
>
>機能拡張はあっても、既存機能の選択肢は狭くなる傾向にあるので、それは大丈夫だと思います。

それは一安心です。

>でも、次期規格は、char16_t型やら_Fract型やら_Accum型などが増えそうなので、内部表現に関してはまた(別の意味で)ややこしくなりそうな予感がします。

なかなか興味深いです。個人的な趣味で使う分には、苦労と同時に楽しみも増えそうな気がします。
(先のグレイコードの例の場合は私の能力の許容量をオーバーしてしまいますけど)
ただ、仕事にするとなると苦労しそうですね。
まあ、周りを見ると、仕事では次期規格どころか、未だにC89(一部C95?)が主流ですし、
C99の存在すら知らない人も多いのが現状ですので、次期規格が出たとしても数年
(もしかすると一生)仕事では関わらなくても済みそうですが。


この投稿にコメントする

削除パスワード

No.6897

Re:符号なし整数型と符号付き整数型の精度の関係
投稿者---yoh2(2006/12/08 21:51:54)


ありゃりゃ。元スレ消されちゃいました。
一応補足しておくと、元スレの質問は、<limits.h>に頼らず、shotr、longの両方に対応した
式をどう表したらいいか、というものでした。


この投稿にコメントする

削除パスワード

No.6898

Re:符号なし整数型と符号付き整数型の精度の関係
投稿者---たかぎ(2006/12/08 22:33:04)
http://takagi.in/


>ありゃりゃ。元スレ消されちゃいました。

結局、掲示板利用宣言を読んでいなかったか、理解できなかったか、誓わずに無視したかのいずれかのようです。



この投稿にコメントする

削除パスワード

No.6900

Re:符号なし整数型と符号付き整数型の精度の関係
投稿者---yoh2(2006/12/08 22:49:54)


肝心な一語が抜けていたので訂正。ついでにtypoも。

× shotr、longの両方に対応した式をどう表したらいいか
○ short、longの両方に対応した、最小値を表す式をどう表したらいいか


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧





掲示板提供:(有)リアル・インテグリティ