Convert binary number 5 into list of intergers (4,1)

Question

I have a configuration value expressed as a binary number to allow several options within the same value.

E.g. the value of 5 would be "101" or both 4 and 1.

Does anyone know of the best/fastest way to "input" the value '5' and get a list of {1,4} back?

Do you mean {4,1} because 4+1 = 5? So If I have 12 I should return {8,4}? 15 = {8,4,2,1} — LuxGiammi, Jun 07 '17 at 12:56
Are your options stored as enum marked with a `FlagsAttribute`? Then this works out of the box. — MakePeaceGreatAgain, Jun 07 '17 at 12:59
@SergeyBerezovskiy: OP is talking about a binary number, so presumably he is splitting it based on binary numbers. 5 (decimal) = 0101 (binary) = 4 + 1 — Flater, Jun 07 '17 at 13:01
Maybe this question will help: https://stackoverflow.com/questions/3261451/using-a-bitmask-in-c-sharp — MakePeaceGreatAgain, Jun 07 '17 at 13:09
Sorry for being unclear as to why it was "4" and "1", but @Flater is correct in his assumption. And thanks for all the answers/suggestions. — Karsten Strøbæk, Jun 08 '17 at 11:57

Sergey Berezovskiy · Accepted Answer · 2017-06-07T13:29:33.417

If you want to get powers of 2 which the value consists of:

int value = 5;
var addendums = Enumerable.Range(0, sizeof(int) * 8 - 1)
                          .Select(i => (1 << i) & value)
                          .Where(x => x != 0)
                          .ToList();

Result:

[ 1, 4 ]

Note that if you want to have addendums in descending order, you can apply Reverse() after filtering sequence.

TL;DR The first step generates integer values which correspond to bit positions in integer value 0, 1, 2, ..., 31. Max index is a number of bits in Int32 value - 1 (because we need the index of the bit).

Next step selects a result of bitwise AND operation of the 1 shifted to the corresponding index (same as the power of 2) with the value itself (only first 4 bits shown here):

i    1<<i     value           (1<<i) & value 
    Binary    Binary       Binary      Decimal
0    0001      0101         0001          1
1    0010      0101         0000          0
2    0100      0101         0100          4
3    1000      0101         0000          0
...

All you have to do after this step - filter out zeroes.

@aloisdg yep, I understand that the order will be from 1 to 2^15. I believe it's up to OP to put numbers in descending order :) — Sergey Berezovskiy, Jun 07 '17 at 13:04

score 1 · Answer 2 · answered Jun 07 '17 at 13:02

Some bit shifting and & later...

int n = 5+32;
var lst = new List<int>();

int i = 1;
while (n > 0)
{
    if ((n & i) == i)
    {
        lst.Add(i);
        n &= ~i;
    }

    i <<= 1; // equivalent to i *= 2
}

A little more esoteric, with the use of xor (^):

if (n != 0)
{
    while (true)
    {
        if ((n & i) != 0)
        {
            lst.Add(i);
            n ^= i;

            if (n == 0)
            {
                break;
            }
        }

        i <<= 1; // equivalent to i *= 2
    }
}

CodeCaster · Answer 3 · 2017-06-07T13:14:01.570

The naive approach:

int originalInput = 42;
int input = originalInput;

// Generate binary numbers
var binaryNumbers = Enumerable.Range(0, 31).Select(n => (int)Math.Pow(2, n)).ToArray();

// Largest first
Array.Reverse(binaryNumbers);

var result = new List<int>();

foreach (var bin in binaryNumbers)
{
    if (input >= bin)
    {
        result.Add(bin);
        input -= bin;
    }
}

Console.WriteLine($"{originalInput} decomposed: " + string.Join(" ", result));

Generate a range of power-of-two numbers, ranging from 2^31 (1073741824) to 2^0 (1), then check whether the input is equal to or larger than those numbers, and if so, add that number to the result list and subtract it from the input.

Now that that's all written out, see how Sergey's answer greatly reduces the code required by some Linq and bitshifting magic.

A hybrid solution, inspired by combining both answers:

var input = 42;

var output = Enumerable.Range(0, 31)
                       .Select(n => (int)Math.Pow(2, n))
                       .Where(p => (p & input) > 0);

Console.WriteLine($"{input} decomposed: " + string.Join(" ", output));

score 0 · Answer 4 · answered Jun 07 '17 at 13:08

I have made this little sample. Here you obtain from an integer its value as a sum of its powers of two. Thosw powers should be your input options

class Program
    {
        static void Main(string[] args)
        {
            var input = 5;
            var options = new List<uint>();

            for (uint currentPow = 1; currentPow != 0; currentPow <<= 1)
                if ((currentPow & input) != 0)
                    options.Add(currentPow);

            foreach (var option in options)
                Console.WriteLine(option);

            Console.ReadLine();
        }
    }

And the output is: 1 4

EDIT>>> In fact this does the same as @Sergey Berezovskiy answer but without LINQ

Hope it helps

score 0 · Answer 5 · answered Jun 07 '17 at 13:14

A maybe more traditional and easy to understand solution. You convert the number into a string binary representation, and then analyze each character to extract the corresponding decimal representations of each bit at 1.

int number = 5;
string binaryRep = Convert.ToString(number, 2);
List<int> myList = new List<int>();
int pow = 0;

for(int i = binaryRep.Count() - 1; i >= 0; i--)
{
    if(binaryRep[i] == '1')
    {
        myList.Add((int)Math.Pow(2, pow));  
    }

    pow++;
}

score 0 · Answer 6 · answered Jun 07 '17 at 13:20

0

Short and fast:

int input = 5;
var list = new List<int>();

for (int i = 1, j = input; i <= j; i *= 2, input >>= 1){
    if ((input & 1) == 1) 
       list.Add(i);
}

answered Jun 07 '17 at 13:20

adjan

13,371
2
31
48

score 0 · Answer 7 · answered Jun 07 '17 at 13:37

To show binary representation use

 int value = 7;
 var binary = Convert.ToString(value, 2);

To see binary numbers:

    private int[] ToBinaryNumbers(int value)
    {
        var binary = Convert.ToString(value, 2).Reverse();
        int ix = 0;
        return binary.Select(x => { var res = x == '1' ? (int?)Math.Pow(2, ix) : (int?)null; ix++; return res; }).Where(x => x.HasValue).Select(x => x.Value).ToArray();
    }

This will give you 1,2,4 for 7 or 1,8 for 9

Convert binary number 5 into list of intergers (4,1)

7 Answers7