Geek asks and answers

What bit is included for an integer in Java

I wrote this code to check which bits are in Integer (if they are presented in binary format) in 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;
}

The code above works fine. But it has a loop that executes 32 times (in Java integer, 32 bits). I want to minimize this complexity. Please share the best solution. Thanks in advance.

+5
source share
5 answers

You can use a bitmask to try to shorten the cycle time. You add a few operations, but maybe do half the cycle:

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;
}

This will potentially increase the time depending on the input.

You can also halve the cycle by doing two bits at a time:

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;
}
+1
source

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;
}

Btw, BitSet?

0

. 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();
}
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- , , . , 1 .

0

Since you know the exact length of an integer, I would recommend using it instead bool[]. However, you can say little about complexity. It is as fast as it can, and the JIT is probably about to unroll this code loop.

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;
}
0
source

More articles:


All Articles