Namaran

Code daily. Without assist.

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。

  1. x86 の BMI2 命令セットにある PDEP(parallel bits deposit)命令は、この関数と同じ計算を1命令で行います。GCC と Clang では <immintrin.h> の _pdep_u32 から使えます。