从数组中获取哪些值构成给定数字之和的算法

Question

我不知道要搜索还是用Google搜索，所以我在这里问。我有一个固定大小的整数数组，并且完全符合此逻辑。

sample [1,2,4,8,16,32]

现在给我一个数字，例如26。然后我将找到其总和将成为该数字的数字，在这种情况下为[2,8,16]

对于20的数字将是[4,16]

40是[8,32]

而对于63来说，所有这些数字[1,2,4,8,16,32]

正确的算法是什么？

我严格知道，此数字始终是先前值的两倍，这是连续存在的。以及仅来自给定数组的数字总和为给定数字，并且每个数字仅使用一次或不使用

如果将在C＃方法中使用int数组和一个int值并返回包含int的int数组，则该int会从给定数组中对该数字求和。

谢谢

Answer 1

如您所见，数字以 2 为基数，这意味着您可以轻松使用shift。

你可以试试这个：

private IEnumerable<int> FindBits(int value)
{
    // check for bits.
    for (int i = 0; i < 32; i++)
    {
        // shift 1 by i
        var bitVal = 1 << i;   // you could use (int)Math.Pow(2, i); instead
        // check if the value contains that bit.
        if ((value & bitVal) == bitVal)
            // yep, it did.
            yield return bitVal;
    }
}

此方法将检查设置了哪些位并将它们作为可枚举的值返回。（可以转换为列表数组）

用法：

// find the bits.
var res = FindBits(40).ToArray();

// format it using the string.join
var str = $"[{string.Join(",", res)}]";

// present the results
Console.WriteLine(str);

结果是[8,32]

额外信息：

                          counter
00000001 =   1     = 1 << 0
00000010 =   2     = 1 << 1 
00000100 =   4     = 1 << 2
00001000 =   8     = 1 << 3
00010000 =  16     = 1 << 4
00100000 =  32     = 1 << 5
01000000 =  64     = 1 << 6
10000000 = 128     = 1 << 7

您不必编写所有组合，而是创建一个执行计数器的 for 循环。

一些额外的废话：

如果您喜欢 lambda，您可以将 FindBits 替换为：

private Func<int, IEnumerable<int>> FindBits = (int value) => Enumerable
    .Range(0, 31)
    .Select(i => 2 << i).Where(i => (value & i) == i);

但最好保持简单/可读。