2 つの整数が同じ符号を持つかどうかを確認する最も簡単な方法は?
-
09-06-2019 - |
質問
2 つの整数が同じ符号を持つかどうかを確認する最も簡単な方法はどれですか?これを行うための短いビット単位のトリックはありますか?
解決
これは、整数のサイズに依存せず、オーバーフローの問題も発生しない、C/C++ で動作するバージョンです (つまり、x*y>=0 は機能しません)
bool SameSign(int x, int y)
{
return (x >= 0) ^ (y < 0);
}
もちろん、凝ってテンプレートを作成することもできます。
template <typename valueType>
bool SameSign(typename valueType x, typename valueType y)
{
return (x >= 0) ^ (y < 0);
}
注記:排他的論理和を使用しているため、符号が同じ場合に LHS と RHS が異なるようにしたいため、ゼロに対する異なるチェックが行われます。
他のヒント
どうしたの
return ((x<0) == (y<0));
?
(a ^ b) >= 0
符号が同じ場合は 1 と評価され、そうでない場合は 0 と評価されます。
整数の符号を決定するためのビット単位のトリックには注意してください。その場合、それらの数値が内部でどのように表現されるかを仮定する必要があるからです。
ほぼ 100% の場合、整数は次のように保存されます。 二人の褒め言葉, ただし、特定のストレージ形式を保証するデータ型を使用している場合を除き、システムの内部について推測することはお勧めできません。
2 の補数では、整数の最後の (左端) ビットをチェックするだけで負かどうかを判断できるため、これら 2 つのビットだけを比較できます。ただし、これは 0 が正の数と同じ符号を持つことを意味しますが、これはほとんどの言語で実装されている符号関数と矛盾します。
個人的には、選択した言語の記号関数を使用するだけです。このような計算でパフォーマンス上の問題が発生する可能性はほとんどありません。
32 ビット整数を仮定すると、次のようになります。
bool same = ((x ^ y) >> 31) != 1;
もう少し簡潔に:
bool same = !((x ^ y) >> 31);
「ビットごとのトリック」と「最も単純な」を同義語と考えるべきかどうかはわかりません。符号付き 32 ビット整数を前提としている多くの回答が見られます (ただし、 するだろう 署名なしを要求するのは愚かです);それらが浮動小数点値に適用されるかどうかはわかりません。
「最も簡単な」チェックは、両方の値が 0 とどのように比較されるかを比較することのようです。これは、型を比較できると仮定すると、非常に一般的です。
bool compare(T left, T right)
{
return (left < 0) == (right < 0);
}
符号が反対の場合は false になります。兆候が同じであれば、それは真実です。
(整数 1 * 整数 2) > 0
2 つの整数が符号を共有している場合、乗算の結果は常に正になるためです。
0 を何があっても同じ符号として扱いたい場合は、>= 0 にすることもできます。
2 の補数算術 (http://en.wikipedia.org/wiki/Two_complement):
inline bool same_sign(int x, int y) {
return (x^y) >= 0;
}
これには、最適化された最新のプロセッサーではわずか 2 命令で 1ns 未満しかかかりません。
2 の補数演算を想定していない場合:
inline bool same_sign(int x, int y) {
return (x<0) == (y<0);
}
これには 1 つまたは 2 つの追加の命令が必要となり、少し時間がかかる場合があります。
乗算はオーバーフローに対して脆弱であるため、乗算を使用することはお勧めできません。
if (x * y) > 0...
非ゼロなどを仮定します。
技術的な注意点として、最新のアーキテクチャであっても、ビット twiddly ソリューションは乗算よりもはるかに効率的になるでしょう。節約できるのはわずか 3 サイクルだけですが、「1 ペニーの節約」についてよく言われることをご存知でしょう...
頭のてっぺんから...
int mask = 1 << 31;
(a & mask) ^ (b & mask) < 0;
ブランチレス C バージョン:
int sameSign(int a, int b) {
return ~(a^b) & (1<<(sizeof(int)*8-1));
}
整数型の C++ テンプレート:
template <typename T> T sameSign(T a, T b) {
return ~(a^b) & (1<<(sizeof(T)*8-1));
}
2 の補数演算を使用した任意のサイズの int の場合:
#define SIGNBIT (~((unsigned int)-1 >> 1))
if ((x & SIGNBIT) == (y & SIGNBIT))
// signs are the same
32ビットだと仮定すると
if(((x^y) & 0x80000000) == 0)
...答え if(x*y>0)
オーバーフローのため不良です
if (a*b < 0) 符号が異なり、else 符号が同じ (または a または b が 0)
大学時代を思い出してみると、ほとんどの機械表現では、整数の左端のビットは、負の場合は 1、正の場合は 0 になるのではないでしょうか?
ただし、これはマシンにかなり依存すると思います。
int Same_sign = !( (x >> 31) ^ (y >> 31) );
if (同じ符号) ...それ以外 ...
より良い使い方 std::signbit 次のように:
std::signbit(firstNumber) == std::signbit(secondNumber);
他の基本タイプもサポートします (double
, float
, char
等)。