2026-09-05
FromGray.hs
fromGray :: Word -> Word
グレイコード g から元の数を返す fromGray を書いてください。数 n のグレイコードは、n と、n を1ビット右へずらした値との xor です。元の数は、g、g を1ビット右へずらした値、2ビットずらした値、……を、0 になるまで順にすべて xor すると得られます。g が 0 なら 0 を返します。
入力例 1
fromGray 6
出力例 1
4
入力例 2
fromGray 7
出力例 2
5
入力例 3
fromGray 0
出力例 3
0
Reference
import Data.Bits (shiftR, xor)
fromGray :: Word -> Word
fromGray g = foldr xor 0 (takeWhile (/= 0) (iterate (`shiftR` 1) g))
iterate (`shiftR` 1) g は、g を1ビットずつ右へずらした値の無限のリストです。takeWhile (/= 0) で 0 になる手前までを取り出し、foldr xor 0 で全部を xor します。g が 0 なら取り出すリストは空で、foldr は初期値の 0 を返します。
この書き方が止まるのは、Word が符号なしで、右へずらすたびに上から 0 が入るからです。型を Int にすると、負の数は右へずらしても符号ビットの 1 で埋められて -1 に行き着き、0 にならないので takeWhile が終わりません。
fromGray 6 なら、110、011、001 を xor した 100 で、4 です。元の数の各ビットは、グレイコードでそのビットより上にあるビットと自分自身をすべて xor したものになっていて、右へずらした値を重ねるとその xor が全ビットで一度に計算されます。
掲載したのは参考実装で、唯一の正解ではありません。明示的な再帰で g を右へずらしながら xor を積み上げても構いません。