Skip to main content

2.2 位元枚舉和遞迴枚舉

位元枚舉介紹

位元枚舉是一種通過遍歷所有的二進制數字來列舉所有可能的狀態的方法。通過對二進制數字中的每一位進行遍歷，可生成所有可能的狀態。

位元枚舉的優勢和定義：

  • 用二進位的方式來簡單維護枚舉的技巧，程式碼量小
  • 通常使用在枚舉部分只有要或不要(1/0)兩種可能，符合二進位原理
  • 例如：10011代表在第1、2、5項要選擇3、4則不選擇

如何使用位元枚舉

進行位元枚舉的基本概念是通過遍歷所有的二進制數字來產生所有可能的狀態。可以通過以下步驟來實作位元枚舉：

  1. 定義好總共有幾項需要枚舉，在此設訂為$n$項
  2. 枚舉所有狀態：用一個循環從$0$開始到$2^n-1$
  3. 根據每次枚舉到的數字來檢查當前狀態的值，1或0來完成不同操作 以下是簡單的位元枚舉範例程式碼
void e(int n) { // 有n項
    for(int i = 0; i < (1 << n); i++) { // 枚舉所有狀態
        for(int j = 0; j < n; j++) { // 各項遍歷
            if((i >> j) & 1) ... // 當前為1
            else ...// 當前為0
        }
    }
}

位元枚舉範例題

https://cses.fi/problemset/task/1623 https://codeforces.com/problemset/problem/1097/B?locale=en

Back to top