Faster way to convert large binary string to BigInteger

Question

The code below is converting big binary string binaryAsString = "1010101011101011......." to BigInteger decimal but this is very slow, it takes very long time to finish. Is there any faster way to make this done? Before this I had a problem with converting BitArray to string. My first code take so long but I found new code which was much faster in a way I didn't imagine. I hope I can find a similarly faster way to do this, because it's really taking a long time.

I tried to use String whatever = Convert.ToString(binaryAsString, 2); but this is not working at all.

// converting the binary String to decimal 
BigInteger Decimalvalue = 0;  

foreach (char c in binaryAsString) 
{
    Decimalvalue <<= 1;

    Decimalvalue += c == '1' ? 1 : 0;

}

I would like to have faster code to do exactly what the code above should do.

You want the string with 0 and 1 to be converted to equivalent decimal number or you want to keep 0 and 1 and covert the string to number ? How big the string can be? — Chetan
– Chetan, Commented May 28, 2019 at 1:04
i want 0 and 1 to be converted to equivalent decimal number . and what u mean by keep 0 and 1 and covert the string to number . very big maybe 1 GB File equivalent but for now is very slow with 1 MB equivalent — zezo alharazi
– zezo alharazi, Commented May 28, 2019 at 1:36
Binary value 11 is 3 in decimal also 11 eleven with 1 and 0 retained — Chetan
– Chetan, Commented May 28, 2019 at 1:56

shingo · Accepted Answer · 2019-05-29 03:22:23Z

1

I think process the large string by each char is not a good way.

char c in binaryAsString

Look at the constructors of BigInteger, you can find:

BigInteger(Byte[])

So the first thing is convert the string into byte array, then construct your big integer. the rest codes are copy from this answer: Convert a binary string representation to a byte array

int numOfBytes = binaryAsString.Length / 8;
byte[] bytes = new byte[numOfBytes];
for(int i = 0; i < numOfBytes; ++i)
    bytes[i] = Convert.ToByte(binaryAsString.Substring(8 * i, 8), 2);

Option 1. Use string.PadLeft

if((binaryAsString.Length % 8) != 0)
{
    var totalWidth = (binaryAsString.Length / 8 + 1) * 8;
    binaryAsString = binaryAsString.PadLeft(totalWidth, '0');
}

Option 2. Convert from tail side

int numOfBytes = binaryAsString.Length / 8;
if((binaryAsString.Length % 8) != 0)
    numOfBytes++;
byte[] bytes = new byte[numOfBytes];
for(int i = 1; i <= numOfBytes; ++i)
{
    int start = binaryAsString.Length - i * 8;
    int length = 8;
    if(start < 0)
    {
        length += start;
        start = 0;
    }
    bytes[numOfBytes - i] = Convert.ToByte(binaryAsString.Substring(start, length), 2);
}

edited May 29, 2019 at 3:22

answered May 28, 2019 at 3:36

shingo

30.1k7 gold badges37 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

zezo alharazi Over a year ago

ok is Decimalvalue = new BigInteger(bytes); , bro this is magical , this is 100000 times faster but there is one problem the ans is not right , i get for Decimalvalue -10292496836912565244.....<< negative number where the ans should be positive = 26257118622826038465... the full number is big am just showing the begging of the number

zezo alharazi Over a year ago

to remove the negative >> To prevent the BigInteger(Byte[]) constructor from confusing the two's complement representation of a negative value with the sign and magnitude representation of a positive value, positive values in which the most significant bit of the last byte in the byte array would ordinarily be set should include an additional byte whose value is 0. so i add this code Decimalvalue = new BigInteger(bytes.Concat(new byte[] { 0 }).ToArray()); but when i want to get the binary back to what it was as binary it's different 0 and 1 i use this to convert it back to binary > below

zezo alharazi Over a year ago

StringBuilder sb = new StringBuilder(); while (Decimalvalue > 0) { sb.Insert(0, Decimalvalue % 2); Decimalvalue /= 2; } /// string RevercBinary = sb.ToString();

shingo Over a year ago

The length is multiple of 8 because every byte has 8 bits. Your input data may trim '0' from the head, so you can use string.PadLeft to add some '0' to make the length of the whole string be 8 times. Another idea is convert this string to bytes from the tail side.

zezo alharazi Over a year ago

both option give me same ans , but i notice something the reason why the 0 and 1 never back the same is coz if i have 00000101 will be convert to 5 , but when i convert it back to binary 5 will be 101 only , how can i get it back to 00000101

|

Lperlind · Accepted Answer · 2019-05-28 04:34:11Z

0

You can use an or operator rather than +.

Further, you can cache the big integer value of 1 (integers are boxed into a big integer)

BigInteger one = 1;
foreach (char c in s)
{
    integer <<= 1;
    if (c == '1')
        integer |= one;
}

It's significantly faster in my tests.

edited May 28, 2019 at 4:34

answered May 28, 2019 at 2:53

Lperlind

12 bronze badges

1 Comment

zezo alharazi Over a year ago

yes this is a bit faster , but for a file of 700kb it take up to 29 mint and still not yet finish , i need faster way

Collectives™ on Stack Overflow

Faster way to convert large binary string to BigInteger

2 Answers 2

8 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related