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

これにより、受信するデータによっては時間が長くなる可能性があります。

一度に 2 ビットを実行することで、ループを半分に減らすこともできます。

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

整数の正確な長さを知っているので、bool[]代わりに a を使用することをお勧めします。ただし、複雑さについてできることはあまりありません。それは可能な限り高速であり、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 に答える