二进制状态压缩枚举子集

  

引言：

二进制数可以用来表示一个状态，比如当我们需要去表示一个集合的子集时，可以用二进制数来表示该子集。

问题

  比如有一个集合，集合中的元素为 {1, 5, 7, 9, 12}，如何快速找到其所有的子集合呢。这就可以采用二进制来压缩该集合，并枚举其所有的子集合状态。

方法一：先二进制压缩，再枚举

public class BinaryStateEnumTest {
    @Test
    public void test() {
        int[] set = {7, 5, 1, 9, 12};
        int binary = 0b100101010001;//12位二进制数。将该集合压缩成一个二进制数。该二进制数从右往左非零元素所在位置对应set中的数

        int status = binary;//最多只有 2^set.length 种状态，每个状态对应一个set的子集
        do {
            System.out.println(getBinaryString(status));
            status = (status - 1) & binary;
        } while (status != binary);//枚举状态包括0，即0b000000000000

        System.out.println("*******************************");

        do {
            System.out.println(getBinaryString(status));
            status = (status - 1) & binary;
        } while (status != 0);//枚举状态不包括0
    }

    private String getBinaryString(int number) {//保证输出长度为12位
        StringBuilder sb = new StringBuilder(Integer.toBinaryString(number));
        while (sb.length() < 12) sb.insert(0, '0');
        return sb.toString();
    }
}

方法二：直接二进制枚举

public class BinaryStateEnumTest {
    @Test
    public void test() {
        int[] set = {7, 5, 1, 9, 12};
        int length = set.length;

        //枚举其子集状态
        for (int i = 0, status = 0; i < (1 << length); i++) {
            for (int j = 0; j < length; j++) {
                if ((i & (1 << j)) != 0) {
                    status |= (1 << set[j] - 1);//最多左移11位，所以是一个12位二进制
                }
            }
            //status是一个12位二进制数表示的状态
            System.out.println(getBinaryString(status));//枚举状态包括0，即0b000000000000
        }

        System.out.println("*********************");

        for (int i = 1, status = 0; i < (1 << length); i++) {
            for (int j = 0; j < length; j++) {
                if ((i & (1 << j)) != 0) {
                    status |= (1 << set[j] - 1);
                }
            }
            System.out.println(getBinaryString(status));//枚举状态不包括0
        }
    }

    private String getBinaryString(int number) {//保证输出长度为5位
        StringBuilder sb = new StringBuilder(Integer.toBinaryString(number));
        while (sb.length() < 12) sb.insert(0, '0');
        return sb.toString();
    }
}