2026-09-05
Subsets.hs
import Data.Bits ((.&.))
subsets :: Integer -> [Integer]
subsets m = takeWhile (/= 0) (drop 1 (iterate (\s -> (s - m) .&. m) 0))
main :: IO ()
main = print (subsets 10)
これは何を出力するでしょうか?
Answer
[2,8,10] です。
iterate は 0 から始めて、s を (s - m) .&. m に置き換え続ける無限のリストを作ります。drop 1 で先頭の 0 を捨て、takeWhile (/= 0) で次に 0 が出たところで止めます。m は 10、2進数で 1010 です。
最初の 0 - 10 は -10 で、ここで負の数が出てきます。Integer のビット演算は、負の数を上位に 1 が無限に続く2の補数として扱うので、-10 は ...10110 です。これと 1010 の .&. は 0010 で、2 になります。続く 2 - 10 = -8 は ...11000 で、1010 との .&. は 8、8 - 10 = -2 は ...11110 で 10 です。最後に 10 - 10 = 0 となってリストが終わります。
2、8、10 は、1010 で立っているビットだけで作れる 0 以外の数を、小さい順に並べたものです。s - m は s + complement m + 1 と同じ値で、s は m のビットしか持たないので、s + complement m は m の外のビットをすべて 1 で埋めた数になります。そこへ 1 を足すと、繰り上がりは m の外の 1 を素通りします。結果は、m のビットの位置だけを使って s に 1 を足したものと同じになり、m の外に残った 1 は .&. m が消します。