从数组中获取哪些值使给定数字的总和的算法

Question

我不知道搜索或谷歌它，所以我在这里问它。我有一个具有固定大小的整数数组，并且完全符合此逻辑。

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#方法中，它接受整数数组和一个整数值并返回包含从给定数组中求和此数字的整数的整数数组将是首选。

谢谢

Answer 1

陈述你的要求的另一种方法是“2的唯一幂和给定整数是什么？”由于计算机本身就使用2的幂，因此在大多数语言中都有内置的好东西可以非常简洁地做到这一点。

另外，您可以使用现有的.Net类型和方法来避免编写自己的循环。

这里有一种方法：

IEnumerable<int> GetCompositePowersOf2(int input) =>
    //convert to enumerable of bools, one for each bit in the 
    //input value (true=1, false=0)
    new BitArray(new[] { input }).Cast<bool>()
    // get power of 2 corresponding to the position in the enumerable 
    // for each true value, gets 0 for false values.
    .Select((isOne, pos) => isOne ? (1 << pos) : 0)
    //filter out the 0 values
    .Where(pow => pow > 0);

Answer 2

首先你应该注意到

 ( 1    2    4    8    16 ... ) = (2^0  2^1  2^2  2^3  2^4 ... )

这和寻找十进制数的二进制编码是一样的。你正在寻找的是一种算法，将十进制或基数为10的数字转换为二进制或基数为2的数字。

算法非常简单:

public List<int> dec_to_bin(int num)
{
    List<int> return_list = new List<int>();
    int index = 0; 
    int remainder = num;
    int bit = 0;

    while (remainder > 0)
    {
        bit = remainder % 2;

        if (bit == 1 )
        {
            return_list.Add((int)Math.Pow(2, index));
        }

        remainder = remainder / 2; 
        index = index + 1;
   }

   return return_list;
}

然而，有一种更好的方法只是使用已经是二进制的数字的底层编码。

public List<int> dec_to_bin(int num)
{
    List<int> return_list = new List<int>();
    int value = 1; 

    while( value < num )
    {
         if( (value & num) == value )
         {
             return_list.Add(value);
         }
         value = value * 2; 
    }
    return return_list;
}

Answer 3

如你所见，数字是以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;
    }
}

此方法将检查设置了哪些位，并将它们作为ienumerable返回。(可以转换成列表数组)

用法:

// 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);

但最好保持简单易读。