Namaran

Code daily. Without assist.

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。

  1. Protocol Buffers の sint32 と sint64 は、この変換をしてから可変長の整数として書き込みます。-1 を int64 としてそのまま書くと10バイトになりますが、ジグザグ符号化した 1 なら1バイトで済みます。