Namaran

Code daily. Without assist.

2026-08-30

FromGray.hs

fromGray :: Int -> Int

0 以上の整数 b に対し、b `xor` (b `shiftR` 1)(Data.Bits の関数で、b と、b を1ビット右へずらした値とのビットごとの排他的論理和)を b の符号と呼ぶことにします。b が1増えるたびに、符号はちょうど1ビットだけ変わります。符号 g を受け取り、符号が g になる元の b を返す fromGray を書いてください。g は 0 以上で、g が 0 なら 0 を返します。

入力例 1

fromGray 6

出力例 1

4

入力例 2

fromGray 13

出力例 2

9

入力例 3

fromGray 0

出力例 3

0
Reference

Reference

fromGray :: Int -> Int
fromGray 0 = 0
fromGray g = g `xor` fromGray (g `shiftR` 1)

符号の各ビットは、b の同じ位置のビットと、その1つ上のビットの排他的論理和です。b の最上位ビットは上に何も無いので、符号の最上位ビットと同じです。その下の b のビットは、符号の同じ位置のビットと、いま求めた1つ上の b のビットの排他的論理和で決まります。これを上から順にたどると、b のあるビットは、符号のその位置から最上位までのビットすべての排他的論理和になります。

g `xor` (g `shiftR` 1) を返したくなりますが、それは符号をもう一度作る計算で、1つ上のビットしか混ぜません。fromGray 13 なら 13 `xor` 6 で 11 になり、9 にはなりません。上のビットすべてを混ぜるには、g、g `shiftR` 1、g `shiftR` 2……を、ずらした値が 0 になるまで排他的論理和でまとめます。参考実装はこれを再帰で書き、fromGray (g `shiftR` 1) が「1つずらした値から先の全部」を受け持ちます。g が 0 以上なら右へずらすたびに小さくなって必ず 0 に着き、そこで 0 を返して止まります。

13 は2進数で 1101 なので、1101、110、11、1 の排他的論理和は 1001 で、9 です。確かめると、9 `xor` 4 は 13 になります。掲載したのは参考実装で、唯一の正解ではありません。foldr xor 0 (takeWhile (> 0) (iterate (`shiftR` 1) g)) のように、ずらした値の列を作ってまとめてもかまいません。