Namaran

Code daily. Without assist.

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 が消します。