从数组中获取哪些值使得它们的总和等于给定数字的算法

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#方法来实现，该方法会接受一个整数数组和一个整数值，并返回包含从给定数组中相加得到该数字的整数的整数数组。

谢谢。

- mister_giga

---

如果有多个可能的组合怎么办？或者这个例子不是故意的，你是在寻找一个数字的“版本”吗？ - Mighty Badaboom

你可以通过数字中的1位来确定需要添加的索引。 - Neil Locketz

@MightyBadaboom 给定的连续性限制了该值仅能有一个组合，而不是更多。 - mister_giga

你真正拥有的是一个2的指数 [1,2,4,8,16,32] = [2^0 ... 2^5]。 - Rahul

@NeilLocketz我不明白你的意思。你可以更好地解释一下吗？ - mister_giga

Answer 1

从上面可以看到，这些数字是以二进制为基础的，因此您可以轻松使用移位操作符。

你可以尝试这样做：

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

但最好保持简单易读。

- Jeroen van Langen

---

我还在写一些额外的信息。你可以阅读它以增加知识;-) - Jeroen van Langen

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

- gbtimmon

Answer 3

另一种表述您的需求的方式是“给定整数，有哪些唯一的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);

- Richard II

Answer 4

我不太理解“接受整数数组”这部分，因为这个求和只适用于2的幂次方。

    private int[] count (int num)
    {

        int factor = 0;
        List<int> facts = new List<int>();
        while (num > 0)
        {
            int counter = 0;
            int div = num;
            int remainder = 0;
            while (remainder == 0)
            {
                remainder = div % 2;
                div = div / 2;
                counter++;
            }
            factor = 1;
            for (int i = 1; i < counter; i++) 
                factor *= 2;
            num = num - factor;
            facts.Add(factor);
        }

        return (facts.ToArray());
    }

- Judit