2026-10-28
nth_combination.cpp
#include <cstdint>
constexpr std::uint32_t nth_combination(std::uint32_t allowed, std::uint32_t k) {
}
機能フラグを1ビットずつ割り当てた32ビットの値で、テストしてよいフラグを allowed に立てます。allowed で立っているビットだけを使ったフラグの組(どのフラグも立てない0を含む)を、整数として小さい順に並べたとき、k 番目(0始まり)の組を返す nth_combination を書いてください。組を並列に試すマシンが、自分の受け持つ番号 k から組を直接求めるための関数で、k は組の総数より小さいとします。組は最大で2の32乗通りあるので、組を小さい順に1つずつ作って数える方法は使えません。
入力例 1
nth_combination(0b1101, 5)
出力例 1
0b1001
入力例 2
nth_combination(0xFFFF0000u, 0xFFFFu)
出力例 2
0xffff0000
入力例 3
nth_combination(0, 0)
出力例 3
0
Reference
constexpr std::uint32_t nth_combination(std::uint32_t allowed, std::uint32_t k) {
std::uint32_t result = 0;
for (std::uint32_t rest = allowed; rest != 0; rest &= rest - 1) {
if (k & 1) {
result |= rest & -rest;
}
k >>= 1;
}
return result;
}
k の2進数の各ビットを、下の桁から順に allowed で立っているビットの位置へ移せば、それが k 番目の組です。入力例1では allowed の 0b1101 で立っている位置が下から0、2、3で、k の 0b101 の3桁をこの3か所に置くと、位置0に1、位置2に0、位置3に1が入って 0b1001 になります。
これで並び順が合うのは、2つの組の大小が、違っているビットのうち最も上のもので決まるからです。2つの組はどちらも allowed の位置にしかビットを持たないので、違うビットも必ず allowed の位置にあります。組から allowed の位置の桁だけを取り出し、下から詰めて並べた数を考えると、組どうしで最も上の違うビットは、詰めた数どうしでも最も上の違う桁になります。そのため、組の大小と詰めた数の大小は一致します。allowed のビットが m 個なら、詰めた数は0から2の m 乗引く1までをちょうど1回ずつ取るので、小さい順で k 番目の組は、詰めた数が k になる組です。
参考実装は、allowed の立っているビットを下から1つずつ取り出し、k の最下位ビットが1ならその位置を result に立てて、k を1桁右へずらします。rest & -rest は rest の最も下の1のビットだけを残した値で、rest &= rest - 1 はそのビットを落とします。符号なし整数の -rest は2の32乗で割った余りとして計算されるので、どちらも未定義動作にはなりません。ループは allowed のビットの数だけ回るので、入力例2の k が65535でも16回で終わります。
掲載したのは参考実装で、唯一の正解ではありません。ビットの位置 i を0から31まで回し、allowed のビット i が立っているときだけ k の次の桁を使う書き方でも同じ値になります1。
- x86 の BMI2 命令セットにある PDEP(parallel bits deposit)命令は、この関数と同じ計算を1命令で行います。GCC と Clang では
<immintrin.h>の_pdep_u32から使えます。