2

Integer の配列内のすべての組み合わせのすべての可能な合計を与えることを目的とするアルゴリズムを取得しました。

private void arraySumPermutation(int value ,int[] arr){
    int N = arr.length;     
    for(int i=0;i<1<<N;i++){
        int sum = 0;                
        for(int j=0;j<N;j++){       

            if((i & 1<<j)>0){
                iCount++;
                sum += arr[j];  
                //S.O.P(sum);
            }
        }

    }
}

ビットごとの AND で追加された内部の if 条件が理解できません。内部ifループの目的は何ですか。

if((i & 1<<j)>0)
4

1 に答える 1

4

N 個の要素セットの組み合わせを N ビットの数値として表現してみましょう。このjビットは、組み合わせに 1j番目のアイテムが含まれる場合は 1、含まれない場合は 0 です。このようにして、すべての可能な組み合わせを範囲 [0, 2 N ) の数値として表すことができます。

外側のループは、これらの数値 ( 1 << N== 2 N ) を反復処理します。

内側のループはセットのアイテムを繰り返し処理し、条件はアイテムが現在の組み合わせに含まれているifかどうかをチェックします。jつまり、 のjth ビットiが 1 かどうかをチェックします。

1<<jj番目のビットのみが 1 である数値を返し、そのビット以外のi & (1 << j)すべてのビットをリセットし、結果が 0 でないことを確認します。i>

このコード ( ints を使用) は N < 31 でのみ機能することに注意してください。

于 2013-01-14T08:00:32.550 に答える