エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary
はじめに この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の1日目の記事です。... はじめに この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の1日目の記事です。 この記事ではビット演算を使って有限集合の部分集合を表現、操作するテクニックを紹介します。 本文中で説明を省略した部分については、詳しい説明のある参考文献を紹介しておきます。 2021/01/03: 高速ゼータ変換/メビウス変換/畳み込みに関する部分を全面的に書き換えました。 表現方法 S={A,B,C,D}という4要素の集合があったとします。 各要素を次のように2進数の数字と対応付けます。 A: 0001 B: 0010 C: 0100 D: 1000 こうすると、Sの部分集合は存在する要素のビットごとの論理和を取ることで4ビットのビット列として一意に表すことができ、例えば {A,B,C}: 0111 {B,D}: 1010 のようになります。 以後、