Zenn
🍲

符号付き整数のビット演算の事例 と 注意点

に公開
C++
C
ビット演算
ビット
tech

これは何？

符号付き整数に対するビット演算は普通しない、という意見を目にしたので、符号付き整数のビット演算が役に立つ事例を書いてみた。

符号なしのときには存在しない罠があるので、その事も書いた。

符号付き整数のビット演算の事例

偶数にしたい・奇数にしたい

符号付き整数を、「奇数だったら最寄りの偶数、偶数ならそのまま」にしたいことがある（あった）。奇数にしたいこともあるだろう。どちらに寄せたいか（大きくしたい、小さくしたい、ゼロに近づけたい、ゼロから遠ざけたい）によって書くべきことが変わるけど、どれでもいいこともある（あった）。

ビット演算をしない場合

C言語
int even = raw / 2 * 2;
int odd = raw - ((raw+1)%2);

のように書けばいいが（注: 古い処理系では raw が INT_MIN などの場合 オーバーフローの危険があるかも）、私としてはビット演算を使った

C言語
int even = raw & ~1;
int odd = raw | 1;

という計算のほうがわかりやすい（個人の感想です）。こちらは古い処理系でも 2の補数表現であればオーバーフローの心配はないと思う。

計算量としては、最適化を前提とすれば 除算 がある前掲のものと大差ないと思う（思うだけ。調べてない）。

4で割ったあまりを知りたい

例えば 90 単位でしか回れないものがあるので、時計回り90度で 1増やし、逆なら 1減らす、と管理する。
今までどんだけ回ったのかが知りたかったりするのであれば、毎回剰余を取るわけには行かない。

累計の向きから、今の向き（4方向のいずれなのか）を計算する際、ビット演算がなければ

C言語
int curDir = ((sumDir % 4 ) + 4 ) % 4;

等とする必要がある。状態が 5種類とかだと上記の感じの計算がよいわけだけど、4種類 であれば

C言語
int curDir = sumDir & 3;

で良い。

平均を取りたい

平均を取るのは意外と難しい。

(a+b)/2 は a+b がオーバーフローするかもしれない。

a+(b-a)/2 だって、b-a がオーバーフローするかもしれない。

ということで

c言語
int mean = (a&b) + (a^b)/2;

という具合のビット演算が必要になる。
私の理解が正しければ、これでオーバーフローせずに符号付き整数の平均が求まる。

この計算は 数学的な平均が整数でない場合にどちら側に寄せるのかが (a+b)/2 とは違うんだけど、どっちでもいい場合はこれでよい。

ゼロ以外になってほしい

0 以外ならそのまま、0 が来ると困るから 1 にする、みたいな局面がたまにある。

c言語
int notZero = canBeZero==0 ? 1 : canBeZero;

などと書けばいいんだけど、

c言語
int notZero = canBeZero | (canBeZero==0);

のほうが、条件分岐風味が少なくて気持ち良いという意見があり得る。

最適化したら同じコードに落ちそうだと思う（試してない。思うだけ）し、あまり賛成はしないけれど。

注意点

シフト演算

あんまりよくわかっていないんだけど、負の値をシフトすると未定義動作になるパターンがある。

私としては「負になる可能性がある場合、シフトはしない」という対応をしていて、それ以上は考えていない。

オーバーフロー

ビット操作内に 加減乗除 を含めたいことがある。

符号なし整数だとオーバーフローしても well defined なんだけど、符号付き整数だとオーバーフローは未定義動作。

ビット操作計算内の加減乗除でオーバーフローするかもしれない場合、諦めて符号なしにしてから計算するのが良い。と思う。

念の為に書いておくと、符号付き整数÷符号付き整数 でオーバーフローすることもある。油断禁物。

符号反転

ビット操作内に 符号反転 を含めたいことがある。

最近調べて知ったんだけど、-x という式は、 x が 符号なし整数の場合 well defined で、 x が符号付き整数の場合、時に未定義動作となる。

未定義動作となるのは x が INT_MIN などの、マイナス側の端っこの値の場合。（2の補数表現でない処理系はまたちがうはず）

未定義動作について

ここまで何度か「未定義動作」と書いてきたわけだけど、その説明をする。

未定義動作っていうのは「手元のコンパイラ・実行環境で動かしてみたら大丈夫だったからOK」とはならない現象なので、数パターン試して問題ないからといって問題ないことには全然ならない。

最適化スイッチで計算結果が変わったり、コンパイラがバージョンアップしたら変わったり、色々ある。
同じ関数を別の場所から呼んだら結果が違うとか、インライン関数にしたら結果が変わったとか、色々ある。

コンパイラが警告してくれることもあるけど、未定義動作になるかどうかが動的に決まる場合（例えば、オペランドが負の場合だけ未定義動作とか）は、警告もしてくれないことが多い。 C/C++ の難儀なポイントだと思う。

たとえば

c++
void test(int x){
    printf( "x: %d, x<0: %s, -x<0: %s\n", 
        x, 
        (x<0 ? "T" : "f"), 
        (-x<0 ? "T" : "f"));
    int b = x&-x;
    printf( "b==INT_MIN: %s\n",(b==INT_MIN ? "T" :"f"));
    printf( "b: %d\n", b);
}

という関数に INT_MIN を渡す場合。

INT_MIN を符号反転しても INT_MIN のままだよ、という処理系だったりすると

  • x は負で、-x も INT_MIN なので負
  • x & -x は INT_MIN & INT_MIN なので INT_MIN

なので

msvc with "-O2" でさっき試した結果
x: -2147483648, x<0: T, -x<0: T
b==INT_MIN: T
b: -2147483648

となったりする。
※ msvc with "-O2" がそう見えるように振る舞ったということで、msvc が「INT_MIN を符号反転しても INT_MIN のままだよ、という処理系」だと確認済みだ、ということではない。

しかし、INT_MIN に符号反転した時点で「鼻から悪魔」なので、たとえば

x86-64 gcc with "-O2" でさっき試した結果
x: -2147483648, x<0: T, -x<0: f
b==INT_MIN: f
b: -2147483648

となる。printf の結果を見ても b は INT_MIN と等しいのに、 b==INT_MIN は false と評価されるような振る舞いとなっている。

これはコンパイラのバグではなく、 C/C++ とはそのようなものなので諦めるしかない。

というわけで、符号付き整数の場合

  • 符号反転する場合、INT_MIN などに注意しないと鼻から悪魔
  • シフトする場合、非負であることを確認してから

あたりに注意しながらビット演算しないとひどい目に合うかもしれない。

他の言語からの移植

Java で動いているビット演算を C/C++ に持ち込む、等の場合、符号付き整数のままで持ち込みたくなるかもしれない。

しかし前述の通り C/C++ には「未定義動作」という鬼が潜んでいるのでそのまま持ち込んでもうまくいくとは限らない。こういう計算は int の長さにだけ注意すれば C# でも Java でも C でも同じだよね、とはならないので気をつけたい。

まとめ

符号付き整数でもビット演算したくなる事例を紹介した。
符号付きの場合、オーバーフローとシフトに注意。
未定義動作は怖い。

Discussion