-1

I am trying to write a c# method which accepts an integer as an input and returns a list of integers which are powers of 2 whose sum is equal to input integer

For example 

Input Integer :15
Output of this should be 1(2^0), 2 (2^1), 4 (2^2), 8 (2^3)
Sum of above integers is 15 = Input Integer


Input Integer :13
Output of this should be 1(2^0), 4 (2^2), 8 (2^3)
Sum of above integers is 13 = Input Integer


Input Integer :8
Output of this should be: 8 (2^3)
Sum of above integers is 15 = Input Integer

May I know a good way to do this?

quetzalcoatl
  • 32,194
  • 8
  • 68
  • 107
DoIt
  • 3,270
  • 9
  • 51
  • 103
  • How would you check if bit `n` of your input integer is 1? Do that for all 32 possible bits (hint: loop) and you have your answer. Give it a try, and if you run into problems, show us the code and ask about that specific problem. – oerkelens Oct 20 '17 at 18:19
  • 1
    Give 'BitArray' a [Chance](https://stackoverflow.com/questions/6758196/convert-int-to-a-bit-array-in-net) and format the output as you need – lokusking Oct 20 '17 at 18:27
  • Please, show some (not) working code you tried. and start looking at [how to ask](https://stackoverflow.com/help/how-to-ask) – Gian Paolo Oct 20 '17 at 19:01
  • @lokusking Got my answer.Thank you – DoIt Oct 20 '17 at 19:21
  • 1
    Do NOT add a solution to your question. Question is a question. Answers and solutions are below. The solution was posted by Dolt - hey, it's you - and that's ok. However, keep it as an answer and when the grace period expires, choose one of the answers and mark it as accepted. It may even be the answer of yours if it looks good and/or other answers were not helpful. – quetzalcoatl Oct 20 '17 at 19:25

3 Answers3

0

The binary representation of the number is literally a bitmap of the powers of 2 that sum to that number. Simply iterate over those bits from LSB to MSB, emitting the appropriate string for each bit that is set to 1.

jwdonahue
  • 6,199
  • 2
  • 21
  • 43
0

Generally, you want a binary representation of your number. The output is the list of positions (counting backwards) on which the representation has ones.

The usual way of implementing this is generally checking the modulo of the division by 2, then dividing by 2 - in a loop.

Piotr Wilkin
  • 3,446
  • 10
  • 18
  • This approach would work for generalized base conversion. For binary though, it's much faster to just use the bitwise operators. – Ben Voigt Oct 20 '17 at 18:23
  • But that's just what the bitwise operations do. Probably all contemporary compilers will optimize division by 2 and modulo by 2 to their respective bitwise operations anyway. No need to provide a specific optimized solution when in most cases it isn't even faster anymore. – Piotr Wilkin Oct 20 '17 at 18:26
  • Unfortunately, division by 2 and modulo by 2 are not equivalent to bitwise operations. A good compiler will try to prove whether the replacement is permitted, but whether that proof succeeds is strongly influenced by the language rules. If looking at bits is what you want, write bitwise operations. – Ben Voigt Oct 20 '17 at 18:30
  • Integer division by 2 (which we are talking about here) is exactly equivalent to a bitwise right shift (unless we take into account negative numbers). Modulo 2 is also a bitwise operation (take the least significant bit). Don't know what you exactly mean by "are not equivalent". – Piotr Wilkin Oct 20 '17 at 18:35
  • "unless we take into account negative numbers"... there's the problem. The compiler will (take them into account). – Ben Voigt Oct 20 '17 at 18:39
0

I got answer through the comments

            var bits = new BitArray(BitConverter.GetBytes(12));
            List<Double> restrictedList = new List<Double>();
            for(int i=0;i<bits.Count;i++)
            {
                if (bits[i]==true)
                {
                    restrictedList.Add(Math.Pow(2, i));
                }
            }
DoIt
  • 3,270
  • 9
  • 51
  • 103