5

我编写了这段代码来检查Java中整数（如果以二进制表示）的哪些位：

public static List<String> list(int val)
{
    List<String> dummyList = new ArrayList<String>();

    int bit = 1;
    int x;

    for(int i=0; i<32; i++)
    {
        x = bit;
        if((x&val)!=0)
            dummyList.add(String.valueOf(i+1));
        bit = bit << 1;
    }

    return dummyList;
}

上面编写的代码工作正常。但它有一个运行 32 次的循环（在 Java 中整数是 32 位长）。我想尽量减少这种复杂性。请分享更好的解决方案。提前致谢。

4

5 回答 5

1

您可以使用位掩码来尝试减少循环次数。您添加了一些操作，但可能会执行一半的循环：

public static List<String> list(int val) {
    List<String> dummyList = new ArrayList<String>();
    int loop = 32;

    // Mask the 16 MSB if all are zero only loop on the 16 LSB
    if((val & 0xFFFF0000) == 0){
        loop = 16;
    }

    int bit = 1;
    int x;

    for (int i = 0; i < loop; i++) {
        x = bit;
        if ((x & val) != 0) {
            dummyList.add(String.valueOf(i + 1));
        }
        bit <<= 1;
    }

    return dummyList;
}

根据传入的数据，这可能会增加时间。

您还可以通过一次执行两个位来将循环减半：

public static List<String> list(int val) {
    List<String> dummyList = new ArrayList<String>();

    int bit = 3;
    int x;

    for (int i = 0; i < 32; i += 2) {
        x = (bit & val);
        switch (x) {
            case 1:
                dummyList.add(String.valueOf(i + 1));
                break;
            case 2:
                dummyList.add(String.valueOf(i+2));
                break;
            case 3:
                dummyList.add(String.valueOf(i+1));
                dummyList.add(String.valueOf(i+2));
                break;
            default:
        }
        val >>= 2;
    }

    return dummyList;
}
于 2013-04-22T23:08:02.143 回答
0

改进O(1)代码似乎微不足道，但此代码略有改进：

public static List<String> list(int val) {
    List<String> dummyList = new ArrayList<String>();
    for (int i=0; val!=0 && i<32; ++i){
        if ((1 << i & val) != 0) {
            dummyList.add("" + (i+1));
            val &= val -1;  // unset the last set bit (current bit)
        }                   // causes loop to end early when all bits are counted
    }
    return dummyList;

与其进行所有 32 位比较，此代码将在计算完最后一位后立即结束。对于用 s 稀疏填充的整数，它的1效率要高得多，而对于高度填充的整数，它的效率也不低。

于 2013-02-02T02:44:30.477 回答
0

由于您知道整数的确切长度，因此我建议您改用 a bool[]。但是，对于复杂性，您无能为力。它尽可能快，而且 JIT 可能无论如何都会展开这段代码的循环。

public static bool[] list(int val)
{
    bool[] a = new bool[32];
    for(int i=0; i<32; i++)
    {
        a[i] = ((1 << i) & val) != 0;
    }
    return a;
}
于 2013-02-02T02:51:10.533 回答
0

复杂度是 O(1)，所以没有太多可以“最小化”的地方。

你的代码没问题..这里稍微重构一下。

public static List<String> list(int val) {
    List<String> dummyList = new ArrayList<String>();
    for (int i = 0; i < 32; i++)
        if ((1 << i & val) != 0)
            dummyList.add("" + (i+1));
    return dummyList;
}

顺便说一句，您是否考虑过使用BitSet?

于 2012-05-09T10:23:32.713 回答
0

32 个循环听起来很适合这个应用程序。如果您想更快地收集数字，可以使用 StringBuffer 而不是 List。

public static String list(int val)
{
    StringBuffer dummyList = new StringBuffer();

    int bit = 1;
    int x;

    for(int i=0; i<32; i++)
    {
        x = bit;
        dummyList.append((x&val) ? '1' : '0' );
        bit = bit << 1;
    }

    return dummyList.toString();
}
于 2012-05-09T10:24:32.737 回答