C# - 1 2 4 8 16 32 64… series - Find the indexes based on input number, recursive function?

Question

I have a series of number as such: [1 2 4 8 16 32 64 128], if I input a number, i.e. 66, then the output should be 64 and 2. If I input 87, then the output should be 64, 16, 4, 2, 1.

(Basically, it first divide by the largest possible number, find the remainder, then keep dividing by the largest number possible, until the remainder is 0. Or another way maybe just to subtract the largest possible number and keep subtracting like that until it reaches 0.)

I'm thinking of a recursive function, but not really sure. Any help?

Thanks.

Answer 1

Here's the iterative version

public static IEnumerable<int> FindIndex(int input)
{
    var power = 0;
    while (input > 0)
    {
        var digit = input % 2;
        if (digit == 1)
        {
            yield return (int)Math.Pow(2, power);
        }
        input /= 2;
        power++;
    }
}

and here's the recursive version

public static void FindIndexRec(int input, int power, ICollection<int> numbers)
{
    if (input == 0)
    {
        return;
    }
    var digit = input % 2;
    if (digit == 1)
    {
        numbers.Add((int)Math.Pow(2, power));
    }
    FindIndexRec(input / 2, ++power, numbers);
}

and you can call it like

var numbers = new List<int>();
FindIndexRec(input, 0, numbers);

Answer 2

class Program
{
    [Flags]
    enum Bits
    {
        _1 = 1,
        _2 = 2,
        _4 = 4,
        _8 = 8,
        _16 = 16,
        _32 = 32,
        _64 = 64,
        _128 = 128
    }

    static void Main(string[] args)
    {
        var b = (Bits)87;
        Console.WriteLine(b);
        Console.ReadKey();
    }
}

Answer 3

You could use bit masks. In fact, scratch that - you should use bit masks! That is almost certainly how the error code was created, and it's how it should be picked apart. Anything else is highly likely to confuse your audience of other programmers.

I make no claims to represent all programmers, nor do I claim to be any good, but I am a programmer, and all the other answers confused me. It's obviously a bitwise "problem", so why obfuscate?

There's no need to even store the result anywhere, since it's as quick to recompute it every time, like so:

for(int i=0;i<8;++i) {
    if((error&(1<<i))!=0 {
        // 1<<i is in the resulting list.
    }
}

Answer 4

    IEnumerable<int> GetFlags(int input,IEnumerable<int> series)
    {
        foreach (int value in series)
            if ((input & value)==value)
                yield return value;
    }

Or LINQ solution to the problem.

IEnumerable<int> GetFlags(int input, IEnumerable<int> series)
{
    return series.Where(x => (x & input) == x);
}

Answer 5

List<int> additives = new List<int>()
List<int> sourceNumbers = new List<int> { 1, 2, 4, 8, 16, 32, 64, 128 };

int sourceNumber = 87;

foreach(var number in sourceNumbers.Reverse())
{
    if(sourceNumber % number > 0)
    {
       additives.Add(number);
       sourceNumber -= number;
    }
    else
    {
       additives.Add(number);
       break;
    }
}

Answer 6

Here's a pretty naive iterated solution in pseudocode. Try to take it somewhere more interesting from here. You can do it recursively, you can convert the integer to binary representation and iterate on that string, id imagine theres a clever way to do it with LINQ very concisely, etc.

v = inputNumber
while(v > 0):
     temp = greatest power of 2 less than v
     print temp
     v -= temp

PS - this does not explictly store the series in question - it presumes powers of 2.

Answer 7

    string calculate(int input)
    {
        string output = string.Empty;
        int[] series = new int[] { 1, 2, 4, 8, 16, 32, 64, 128 };
        foreach (int i in series.Reverse<int>())
        {
            if (input >= i)
            {
                output += i.ToString() + " ";
                input -= i;
            }
        }
        return output;
    }

Answer 8

This one will work with input numbers greater than 256:

   int[] calculate(int input)
    {
        List<int> retVal = new List<int>();
        string output = string.Empty;
        int[] series = new int[] { 1, 2, 4, 8, 16, 32, 64, 128 };
        foreach (int i in series.Reverse<int>())
        {
            while (input >= i)
            {
                retVal.Add(i);
                input -= i;
            }
        }

        return retVal.ToArray();
    }

Ex: var result = calculate(284); // result = 128, 128, 16, 8, 4

Answer 9

Programming aside, you can also look at it mathematically. It's basically 2 to the power of (integer value of) log(2, input)

Putting this in a recursive function would be easy ofcourse, it would even look simple and smooth, but I doubt it being less computationally complex and it sure doesn't help with your homework, just thought I would throw it here.