java生成从1到2^k1的数字的二进制表示形式

Question

我想获得一个范围为1的二进制整数列表。。。2^k-1。否则，我需要一个k位的所有可能组合的列表。例如，假设k是3，我需要：

001
010
011
100
101
110
111

当我计划在Java中这样做时，我考虑使用一个位集来表示每个数字，并在列表中存储一个值，但我认为这个问题可能与语言无关。基本上，我需要找出生成整个集合的算法

我想我需要一个递归的解决方案，考虑到之前设置的位

void fill(int k, int i, boolean wasSet) {
    if (i==k) return;
        BitSet bs = new BitSet();
        for (int j=0; j<k; j++) {
          if (!wasSet) {
              bs.set(i);
              fill(k, i, true);
          } else {
              fill(k, j, false);
          }
    }

注意：这个函数原型显然是非常错误的

注2：我真的希望避免使用字符串，因为我以后需要使用这个值来执行其他一些计算，而位集在这方面非常方便

Answer 1

您可以拥有以下内容：

for(int i=0 ; i<n ; i++){
  System.out.println(Integer.toBinaryString(i));
}

其中n是您想要的最大数字

更新

要使用BitSet，java7有一个BitSet.valueOf(byte[])和BitSet.toByteArray()

有关更多详细信息，请参阅this post

Answer 2

那么，您可以始终手动递增：

int k = 3; //or something else

ArrayList<Boolean[]> combinations = new ArrayList<>();

boolean[] current;

void increment() {
    for(int i = 0; i<k; i++) {
        if(current[i]) {
            current[i] = false;
        } else {
            current[i] = true;
            break;
        }
    }
}

void fill() {
    current = new boolean[k];
    combinations.add(current);
    final int max = (int) Math.pow(2, k);
    for(int i = 1; i< max; i++) {
        current = current.clone(); //not sure about this -> google java array copy/clone
        increment();
        combinations.add(current);
    }
}

这将把LSB（最低有效位）放在地址0处，但由于它包含所有组合，这不重要，只有当您将其表示为MSB（most-| |-）将在索引0处时，才会对其进行排序

Answer 3

import java.util.LinkedList;
import java.util.Queue;

public class GenerateBNo 
{
    static void generatePrintBinary(int n)
    {
        Queue<String> q = new LinkedList<String>();
        q.add("1");
        while(n-- > 0)
        {
            String s1 = q.peek();
            q.remove();
            System.out.println(s1);
            String s2 = s1;
            q.add(s1 + "0");
            q.add(s2 + "1");
        }
    }
    public static void main(String[] args) 
    {
        int n=10;
        generatePrintBinary(n);
    }
}

Answer 4

下面是我提出的递归解决方案

它只是针对每个位置尝试设置该位，然后递归

它对所有置换使用相同的BitSet。如果您希望每个都有一个，您可能需要复制它

static BitSet bs = new BitSet(3);   
static void fill(int k, int n)
{
   if (k == n)
   {
      System.out.println(bs);
      return;
   }
   bs.set(k, false);
   fill(k+1, n);
   bs.set(k, true);
   fill(k+1, n);
}

public static void main(String[] args)
{
    fill(0, 3);
}

Answer 5

这里有一个简单的解决方案，它相当于遍历一个完整的二叉树并记录每条路径

public class Combinations {

    public static void combinations(int i,int k,char[]buff) {
        if(i<k) {

            buff[i] = '0';
            combinations(i+1,k,buff);
            buff[i] = '1';
            combinations(i+1,k,buff);
        }
        else System.out.println(String.valueOf(buff));
    }

    public static void main(String[] args) {
        int k = 3;
        combinations(0,k,new char[k]);
    }

}

Answer 6

奇怪的问题，一些先进的概念，但还有一些逻辑空白

尽管如此，如果您想要为每个值设置位集，请执行相同的操作（如tokhi建议的）：

int size = 1 << bits;
ArrayList<BitSet> results = new ArrayList<>(size);
for (int val = 1; val < size; val++) {
    BitSet bs = new BitSet(bits);
    results.add(bs);
    for (int b = 0; b < bits; b++) {
        if ( ((val >>> b) & 1) == 1) {
           bs.set(b);
        }
    }
}

---

编辑

在一些关于递归或循环是否更好的“聊天”之后，我已经完成了这个测试

我对上面的代码进行了修改，使其效率稍高一些，但是，我对Dukeling的代码进行了较大的修改，使其返回所有位集，而不是只修改一个位集而不存储结果

请注意，递归代码中存在一个“bug”，因为它返回不应该是结果的一部分的no bits set值

无论如何，这只是一个值得思考的问题

以下是我的测试代码：

import java.util.ArrayList;
import java.util.BitSet;

public class Junk {

    private static final ArrayList<BitSet> loop(final int bits) {
        int size = 1 << bits;
        ArrayList<BitSet> results = new ArrayList<>(size);
        for (int val = 1; val < size; val++) {
            BitSet bs = new BitSet(bits);
            results.add(bs);
            int v = val;
            int b = 0;
            while (v != 0) {
                if ( (v & 1) == 1) {
                   bs.set(b);
                }
                b++;
                v >>>= 1;
            }
        }
        return results;
    }

    private static final ArrayList<BitSet> recurse(final int bits) {
        ArrayList<BitSet> retval = new ArrayList<BitSet>();
        BitSet bitset = new BitSet(bits);
        fill(bitset, 0, bits, retval);
        return retval;
    }


    private static final void fill(final BitSet bs, final int k, final int n, final ArrayList<BitSet> results)
    {
       if (k == n) {
          results.add((BitSet)bs.clone());
          return;
       }
       bs.set(k, false);
       fill(bs, k+1, n, results);
       bs.set(k, true);
       fill(bs, k+1, n, results);
    }

    private static final void exercise(final int bits) {

        double acnt = 0;
        double bcnt = 0;
        long atime = 0L;
        long btime = 0L;

        for (int i = 0; i < 1000; i++) {
            final long as = System.nanoTime();
            acnt += recurse(bits).size();
            atime += System.nanoTime() - as;
            final long bs = System.nanoTime();
            bcnt += loop(bits).size();
            btime += System.nanoTime() - bs;
        }

        acnt /= 1000;
        bcnt /= 1000;

        System.out.printf("    Bits %d: ms/call -> recurse %.3fms loop %3fms (recurse %.1f/%d loop %f.1/%d\n",
                bits, atime / 1000000.0, btime / 1000000.0, acnt, 1<<bits, bcnt, (1 << bits) - 1);
    }

    public static void main(String[] args) {
        System.out.println("warmup");

        exercise(3);
        exercise(2);
        exercise(1);

        System.out.println("real runs");

        exercise(1);
        exercise(2);
        exercise(3);
        exercise(4);
        exercise(5);
        exercise(6);
        exercise(7);
        exercise(8);
        exercise(9);
        exercise(10);
        exercise(11);

    }

}

这是我机器上的输出：

warmup
Bits 3: ms/call -> recurse 12.324ms loop 7.109403ms (recurse 8.0/8 loop 7.000000.1/7
Bits 2: ms/call -> recurse 2.949ms loop 2.392226ms (recurse 4.0/4 loop 3.000000.1/3
Bits 1: ms/call -> recurse 1.681ms loop 1.038053ms (recurse 2.0/2 loop 1.000000.1/1
real runs
Bits 1: ms/call -> recurse 1.743ms loop 0.865739ms (recurse 2.0/2 loop 1.000000.1/1
Bits 2: ms/call -> recurse 1.996ms loop 0.261967ms (recurse 4.0/4 loop 3.000000.1/3
Bits 3: ms/call -> recurse 3.150ms loop 0.544942ms (recurse 8.0/8 loop 7.000000.1/7
Bits 4: ms/call -> recurse 4.876ms loop 0.932031ms (recurse 16.0/16 loop 15.000000.1/15
Bits 5: ms/call -> recurse 6.128ms loop 1.775841ms (recurse 32.0/32 loop 31.000000.1/31
Bits 6: ms/call -> recurse 9.937ms loop 3.209335ms (recurse 64.0/64 loop 63.000000.1/63
Bits 7: ms/call -> recurse 21.005ms loop 7.221974ms (recurse 128.0/128 loop 127.000000.1/127
Bits 8: ms/call -> recurse 38.715ms loop 16.410275ms (recurse 256.0/256 loop 255.000000.1/255
Bits 9: ms/call -> recurse 69.904ms loop 41.330404ms (recurse 512.0/512 loop 511.000000.1/511
Bits 10: ms/call -> recurse 132.053ms loop 88.952120ms (recurse 1024.0/1024 loop 1023.000000.1/1023
Bits 11: ms/call -> recurse 255.921ms loop 193.370808ms (recurse 2048.0/2048 loop 2047.000000.1/2047