集合的整数表示——二进制表示法

超、凢脫俗 2022-09-02 11:49 295阅读 0赞

使用情况

只有当集合中的元素比较少的时候，才能用这种方法来表示。

原理

f(S) = sum(2^i)，
其中，i为属于集合的元素的所有下标。

用法

空集 —— 0
只含第i个元素的集合 —— 1<> i & 1)
向集合中加入第i个元素 —— S | 1 << i
从集合中去除第i个元素 —— S & ~(1 << i)
合并集合S与T —— S | T
集合S与T相交 —— S & T

举例

1. 枚举任意集合sup的所有子集

  1. int sub = sup;
  2. do 
  3. {
  4.     sub = (sub - 1) & sup;
  5. } while(sub != sup);

处理完0之后，会有-1 & sup =sup，满足截止的条件

2. X&(-X) —— 取出最低位的1

因为-X实际上对应着（~X） + 1的补码

因此，X & (-X)可以取出X化为二进制数后的最低位的1

3. 枚举{0,1,…,n-1}所包含的所有大小为k的子集

要求：按照字典序升序枚举出所有满足条件的二进制码

  1. int comb = (1 << k) - 1;
  2. while (comb < 1 << n)
  3. {
  5.     int x = comb & -comb;
  6.     int y = comb + x;
  7.     comb = ((comb & ~y) / x >> 1) | y;

发表评论

表情：
评论列表 （有 0 条评论，295人围观）

还没有评论，来说两句吧...

相关阅读