要素数kの部分集合を表すビット列の全列挙方法について

長さ $n$ でちょうど$k(<n)$ビットが$1$になっているビット列を全列挙する方法が知りたかったので調べていたところ、以下のような実装が見つかった。（参照：ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜）

function nextCombination(bit: number) {
  const x = bit & -bit;
  const y = x + bit;
  return y | (( (bit & ~y) / x ) >> 1)
}

const n = 5;
const k = 3;

for ( let bit = (1 << k) - 1; bit < (1<<n); bit = nextCombination(bit) ) {
  // 処理
}

$\{ 0, 1, 2, 3, 4 \}$の部分集合のうち要素数が$3$であるものが以下のような順で辞書順昇順に列挙されるらしい。

数値	ビット列	対応する集合
7	111	$\{ 0, 1, 2 \}$
11	1011	$\{ 0, 1, 3 \}$
13	1101	$\{ 0, 2, 3 \}$
14	1110	$\{ 1, 2, 3 \}$
19	10011	$\{ 0, 1, 4 \}$
21	10101	$\{ 0, 2, 4 \}$
22	10110	$\{ 1, 2, 4 \}$
25	11001	$\{ 0, 3, 4 \}$
26	11010	$\{ 1, 3, 4 \}$
28	11100	$\{ 2, 3, 4 \}$

nextCombinationで次の組み合わせを表すビット列を作っているが、最初何をやっているか分からなかった。
x = bit & -bitでbitの最下位ビットのみが立っているビット列が得られることは知っていたのですぐ分かったが、2, 3行目の意味が分かりにくい。

とりあえずnextCombinationの処理を追ってみると以下のようになった。

入力	x	y	bit & ~y	( (bit & ~y) / x ) >> 1	出力
111	1	1000	111	11	1011
1011	1	1100	11	1	1101
1101	1	1110	1	0	1110
1110	10	10000	1110	11	10011
10011	1	10100	11	1	10101
10101	1	10110	1	0	10110
10110	10	11000	110	1	11001
11001	1	11010	1	0	11010
11010	10	11100	10	0	11100
11100	100	100000	11100	11	100011

どうやら、nextCombinationは上位側と下位側のビット列を別々に作って合わせることをしているらしい。以下はその説明。

まず、入力bitに対して、x = bit & -bitでbitの最下位ビットが立つビット列を作る。
このxをbitに足すことで、bitの最下位側に並ぶ$1$を$0$にし、さらにすぐ左の$0$を$1$にできる。
最下位側に並ぶ$1$とそのすぐ左の$0$以外に手を加えていないので、y = x + bitは出力ビット列のうち上位側を表すビット列になることが分かる。

あとは下位側だが、yでは元のbitより$1$が1つ増えているので、下位側ではその分減らす必要がある。
bit & ~yでbitの下位側のビット列を得る（→ 11...100..0という形になる）。
xで割ることで末尾の$0$をちょうど消すように右にシフトできる（→ 11...1という形になる）。
さらに>> 1で1シフトすることで$1$の数を減らすと求める下位側のビット列が得られる。

辞書順に列挙しているので最後はビット列の長さが$n$を超えた時点で終了すればよい。