title: 集合的二进制操作
toc: true
original: true
date: 2016-01-02 17:35:52
tags:
- 算法
- 数学
categories:
- 学习笔记
mathjax: true
---
## 集合与二进制
前面的代码里([【开关问题】POJ 3276 3279 3185 1222](/2016/01/01/【开关问题】POJ-3276))可以看到一些为了枚举所有状态用到了集合的整数表现与位操作。
虽然位操作枚举比较简单但是这种方法只能在元素比较少的情况下(20个左右)使用。
假设集合有$N$个元素,依次给它们编号$0, 1, \cdots, N-1$,由于每个元素在集合中只有两种状态:**存在**或者**不存在**。那么可以令相应二进制位来表示,存在则为1,否则为0。
举个例子,8个元素编号依次为$0, 1, \cdots, 7$,那么编号为$\lbrace 0, 2, 4\rbrace $的集合可以用{% raw %}$S = (00010101)_2 = (21)_{10} % 注意下标${% endraw %}来表示。那么空集$\varnothing$可用{% raw %}$S = (00000000)_2 = (0)_{10}${% endraw %}来表示(即都不存在),同理全集可用{% raw %}$S=(11111111)_2 = (255)_{10} = 2^8 - 1${% endraw %}表示。
## 集合的操作
像这样表示之后,一些�