2026-09-05
ZigZag.hs
import Data.Bits (shiftL, shiftR, xor)
import Data.Int (Int64)
import Data.Word (Word64)
zigzag :: Int64 -> Word64
zigzag n = (w `shiftL` 1) `xor` (w `shiftR` 63)
where
w = fromIntegral n
main :: IO ()
main = print (map zigzag [0, -1, 1, -2])
符号つきの整数 0, -1, 1, -2, … を、符号なしの 0, 1, 2, 3, … へ順に移す zigzag です。map zigzag [0, -1, 1, -2] は、いま [0,18446744073709551615,2,18446744073709551613] を返します。本来は [0,1,2,3] です。
Answer
Wrong
zigzag n = (w `shiftL` 1) `xor` (w `shiftR` 63)
where
w = fromIntegral n
w は Word64 なので、shiftR は空いた上位のビットを 0 で埋めます。w `shiftR` 63 は符号ビットを最下位へ下ろしただけの 0 か 1 にしかなりません。-1 なら w はすべて 1 のビット列で、左へ1つずらすと ...1110 になり、そこへ 1 を xor すると ...1111、つまり 18446744073709551615 です。0 以上の数は右シフトの結果が 0 で、n の2倍がそのまま返るので、1 は正しく 2 になります。
Right
zigzag n = fromIntegral ((n `shiftL` 1) `xor` (n `shiftR` 63))
Int64 のまま右へ 63 ずらすと、符号つきの型の shiftR は上位を符号ビットで埋めるので、結果は負の数ならすべて 1、0 以上ならすべて 0 になります。すべて 1 との xor は全ビットの反転なので、-1 を左へずらした ...1110 は 1 に、-2 の ...1100 は 3 になります。Word64 への変換は、ビットの操作が済んでから最後に一度だけ行います1。
- Protocol Buffers の
sint32とsint64は、この変換をしてから可変長の整数として書き込みます。-1をint64としてそのまま書くと10バイトになりますが、ジグザグ符号化した1なら1バイトで済みます。