java - 了解按位条件检查以获取传递的数组中所有可能的组合总和

Question

我有一个算法，其目标是给出整数数组中所有组合的所有可能和。

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)

Answer 1

让我们将 N 元素集的组合表示为 N 位数字，其中 j如果 j 第 1 位为 1第一项包含在组合中，否则为 0。这样您就可以将所有可能的组合表示为 [0, 2^N) 范围内的数字。

外循环迭代这些数字 ( 1 << N == 2^N)。

内循环迭代集合中的项目和 if条件检查是否 j该项包含在当前组合中。换句话说，它检查是否 j i 的第 1 位是 1。

1<<j给你一个数字，其中只有 j第 1 位为 1，i & (1 << j)重置 i 的所有位除了那一点，和 >检查结果是否不为 0。

请注意，此代码(带有 int )仅适用于 N < 31。