JavaScript/Elm ビット演算のときにはまったこと

結論

JavaScriptにおいて、>>>以外のビット演算は32ビット符号付き整数値として扱われる。
→ 例えば&|^~の計算前に、オペランドに型変換が起こる(ソース)。
- JSにおいて数字はNumberという型しかないが、ビット演算のときだけ32ビット整数値に変換されるっぽい
JavaScriptにおいて、x >>> 0を使うと符号なし整数になる。
負数を2で割り続けても、コンピュータにおける2進表現にはならない。
- これはすごく当たり前だった
- コンピュータにおける2進数表現にしたいなら，論理シフトを使うこと。
ElmはJavaScriptに変換されるので、上の事実はすべてElmでも当てはまる。
- 各種ビット演算は、JSの演算をそのまま使っているっぽい(ソース)

検証コード

$ elm init

src/MyBitwise.elmを作成し、内容を以下のようにする。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
module MyBitwise exposing (..)

import Bitwise

toBinaryString : Int -> String
toBinaryString x =
  let bit = Bitwise.and x 1
      rem = Bitwise.shiftRightZfBy 1 x
  in
  if rem > 0 then
    (toBinaryString rem) ++ (String.fromInt bit)
  else
    String.fromInt bit

elm replを起動し、試す。まず必要なモジュールをimportする。

$ elm repl
> import Bitwise
> import MyBitwise exposing (..)

2³²-1 = 4294967295を2進表示すると、1が32個並んだ数になる。32ビット整数の2の補数表現では、-1と4294967295は同じ表現方法になる。

> toBinaryString 4294967295
"11111111111111111111111111111111" : String
> toBinaryString -1
"11111111111111111111111111111111" : String

Bitwise.andの計算結果は符号付き整数値とみなされるので、以下では4294967295ではなく-1と出力される。

> Bitwise.and 4294967295 4294967295
-1 : Int

ここで、MyBitwise.elmにて次の関数を定義する。ビットシフトの部分を2でのmodと割り算に置き換えただけ。

1
2
3
4
5
6
7
8
9
toBinaryStringWrong : Int -> String
toBinaryStringWrong x =
  let bit = modBy 2 x
      rem = x // 2
  in
  if rem > 0 then
    (toBinaryString rem) ++ (String.fromInt bit)
  else
    String.fromInt bit

2つの関数の計算結果を比べてみると、toBinaryStringWrongの結果が1になってしまい、これはおかしい。

> toBinaryString (Bitwise.and 4294967295 4294967295)
"11111111111111111111111111111111" : String
> toBinaryStringWrong (Bitwise.and 4294967295 4294967295)
"1" : String

ちなみに符号なし整数に変換するには、次のようにする。

1
2
3
showAsUnsigned : Int -> Int
showAsUnsigned x =
  Bitwise.shiftRightZfBy 0 x

> showAsUnsigned -1
4294967295 : Int

考えるに至った背景

IPアドレスとサブネットマスクからネットワーク部を算出するプログラムを書いていたら、この状況に出くわした。

IPアドレスは次のように持っているものとする。

1
2
3
4
5
6
7
8
type IPAddr = IPAddr Int
type DotDecimalNotation = DDN Int Int Int Int

fromDDN : DotDecimalNotation -> IPAddr
fromDDN ddn =
  case ddn of
    DDN a b c d ->
      IPAddr (2^24*a + 2^16*b + 2^8*c + d)

サブネットマスクからネットワーク部を算出する関数を定義する。

1
2
3
4
5
6
7
networkAddrBy : IPAddr -> IPAddr -> IPAddr
networkAddrBy subnet addr =
  case subnet of
    IPAddr s ->
      case addr of
        IPAddr a ->
          IPAddr (Bitwise.and s a)

ここまではいいのだが、次のようにしてDDNに変換する関数を定義したところ、バグらせた。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
toDDNHelp : Int -> (Int, Int)
toDDNHelp n =
  (modBy (2^8) n, n // (2^8))

toDDN : IPAddr -> DotDecimalNotation
toDDN addr =
  case addr of
    IPAddr n0 ->
      case toDDNHelp n0 of
        (d, n1) -> 
          case toDDNHelp n1 of
            (c, n2) -> 
              case toDDNHelp n2 of
                (b, n3) -> 
                  case toDDNHelp n3 of
                    (a, _) -> 
                      DDN a b c d

以下で、192.168.1.1と255.255.255.0の論理和をとって193.169.1.0となるわけがないのでおかしい。

> networkAddrBy (fromDDN (DDN 192 168 1 1)) (fromDDN (DDN 255 255 255 0))
IPAddr -1062731520 : IPAddr
> networkAddrBy (fromDDN (DDN 192 168 1 1)) (fromDDN (DDN 255 255 255 0)) |> toDDN
DDN 193 169 1 0
    : DotDecimalNotation

これはtoDDNHelpに問題があり、次のようにシフトを使って書き直すとうまくいく。

1
2
3
4
5
toDDNHelp : Int -> (Int, Int)
toDDNHelp n =
  (Bitwise.and (2^8-1) n
  ,Bitwise.shiftRightZfBy 8 n
  )

> networkAddrBy (fromDDN (DDN 192 168 1 1)) (fromDDN (DDN 255 255 255 0)) |> toDDN
DDN 192 168 1 0
    : DotDecimalNotation

はじめElmのBitwise.andがバグってるんじゃないかと思ってデバッグしていたら、どうやらJSの仕様だということが判明。

型変換の怖さを味わった良い機会だった。Elm側でIntの符号付きと符号なしの区別をうまくしてほしいな、と思った。

結論#

検証コード#

考えるに至った背景#

結論

検証コード

考えるに至った背景