2012年3月16日金曜日

左シフト演算子と未定義動作

指定したビット数だけ下(LSB)からビットが立ったビットマスクを得るために

(1U << bits) - 1

という式を愛用していたのだがはまってしまった。bits == std::numeric_limits::digits つまり全て 1 のマスクにしたい場合、この式は未定義動作をもたらす。14882:2003 5.8/1 には(右シフトも含めて一般に)こうある。

The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

そして実際に少なくとも x86 上ではまず期待通り(全て 1)にはならない。x86 アセンブリの左シフト命令はシフト数は 5 ビット分だけ有効である。つまり 32 == 100000(2) は 0 ビットシフトと同じになり結果として上の式は 1 - 1 == 0 となってしまう。

左シフトには他にも未定義動作となる場合があるのだがこの記述にも変遷がある。

14882:1998 と 14882:2003 では以下の通りである。つまり undefined behavior という記述がない。E1 が signed な場合はどうなるのが正しいんだよ、という感じである。恐らく未定義動作を意図していない記述だろう。

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ]

一方、14882:2011 (多分。自分の参照文書は n3291 なので違う場合もあり得る)では DR854 によりこうなっている。

The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2 × 2E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise. [Note: the constants ULONG_MAX and UINT_MAX are defined in the header <climits>). ] one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1×2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

int, long int よりも大きな型も想定した記述となっていること、E1 が signed な場合にも記述が明確となり、負の場合には未定義動作となっている。

そして、既に DR1457 が出ており以下のように修正される予定である。

if E1 has a signed type and non-negative value, and E1 × 2E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

これは、1 << std::numeric_limits::digits のように最大の負数を得るためにビット数-1(=符号ビット分少ないビット数)だけシフト、つまり符号ビットを 1 にするコードを合法にするためである。ただし、これは signed の範囲で表現できない unsigned の値から signed への変換について処理系定義の動作を含む。……しかしだったら signed 全体について全て unsigned にして処理した後 singed に戻すとか規定してしまえばいいじゃないかとも思う。

なお、右シフトについては実質的に記述は変わっておらず(文による表現が式による表現になっただけ)、E1 が負数の場合は処理系定義となっている(以下は n3291 より)。

The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

0 件のコメント:

コメントを投稿