インプルの芝田です。
今日はシフト演算の桁あふれについて考えてみたいと思います。
背景
某案件の処理において、期待通りの挙動をしなかったため原因を特定していると、シフト演算の桁あふれによるものだったので書いてみようと思いました。
準備＆前提条件
いくつか準備をします。
- 数字を用意する
手を動かして再現できるように数字を用意します。16進数の3429という数字（10進数では13353）を考えます（実際に私が計算した例なので今回こちらを使用します）。 - 記法について
3429(16)のように、括弧内の数字が基数を表すものとします。 - 言語について
js(react native)を使用していました。 - 計算範囲について（重要）…（♪）
今回計算する範囲は、2バイトのバイナリ（つまり16ビット分）で行うという前提があります。
検証
この3429(16)を次の手順に従って計算（実際はデコードです）していき、988(10)になるかどうか確認します。
※こちらの手順に則って計算すると理論上は一致するはずでした。しかし、何度確認しても結果が一致しなかったため、手計算も使って動作を確認した次第でした。
では、下記を確認していきましょう。
- 3429(16)を2進数で表記する
- B452(16)を2進数で表記する（こちらはあらかじめ与えられたものです）
- 上記でXORを取る
- 3に対して、左３シフトを実行する
- 3に対して、右１３シフトを実行する
- 4と5で得られた数に対してORを取る
3429(16)を2進数で表記する
3429(16)は、2進数では次のようになります。
11 010 000 101 001B452(16)を2進数で表記する
B452(16)は、2進数では次のようになります。
1 011 010 001 010 010上記でXORを取る
1と2でXORを取ります。すると、2進数では以下のようになります。
1 000 000 001 111 011※「参考」のセクションにも載せましたが、具体的な計算は以下サイトを利用させていただくと便利です。
https://yanohirota.com/bitwise-operator/
（2023/04/03現在、上記のサイトは304エラーで閲覧できないようです。）
3に対して、左３シフトを実行する
3に対して左３シフトを実行します。
1 000 000 001 111 011 0003に対して、右１３シフトを実行する
3に対して右1３シフトを実行します。
1004と5で得られた数に対してORを取る
1 000 000 001 111 011 000と
100でORを取るので、
1 000 000 001 111 011 100となりました。（10進数では263132ですね）
10進数では988となることを期待していたのに、なぜ263132とここまで大きく開いた値が出てきてしまったのでしょうか。
なぜ？？
タイトルにも記載したので皆さん気づいていらっしゃるかと思いますが、根本的な原因は上記ステップの4にあります。（♪）で記載したように、計算範囲は16ビットまでとしていましたが、jsでは32ビットまでを許容しているので左シフトで19ビット目が立ってしまいました。これが計算結果が大きくずれる原因でした。
※ちなみに、19ビット目の1を無視して
1 111 011 100で計算すると期待した988となっていることが確認できます。
最後に
jsのビット演算は32ビットまで扱えること、16ビットの範囲内で考えるという前提のはずなのに、論理の時点で16ビットを超えてしまうということ。この二点が根本的な原因でした。
一方、シフト演算は10年以上前に基本情報技術者試験の問題に取り組んでいるときに初めて出会ったと記憶しています。
それからいろいろな案件に携わってきましたが、シフト演算を考慮する案件は携わったことがありませんでした。
ただ、10年以上も前に勉強した内容が「確かシフト演算って桁あふれって現象起こったような…」という記憶から今回の事象の解決に結び付けられたと考えると、やはりいくつになっても勉強が大切だなと実感しています。
今後も新しい技術のキャッチアップ含め、日々ステップアップしていきたいと思います。
参考
すべて手計算するのは手間なので、基数の変換やXORととるような処理は次のサイトで計算できます。
※上記のサイトは2023/04/03現在、304エラーで閲覧できないようです。
代わりに以下などを参照してください。
