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, May 28 '19 at 01: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, May 28 '19 at 01:36
Binary value `11` is `3` in decimal also `11` eleven with `1` and `0` retained — Chetan, May 28 '19 at 01:56
https://www.sanfoundry.com/csharp-programs-convert-binary-decimal/ — Chetan, May 28 '19 at 01:58
You can visit the link I shared to get the logic of how to convert binary to decimal — Chetan, May 28 '19 at 02:02
the link does not help . my code already do the converting right , i just want faster way to do so . + the link is for int binary and maximum five digits binary — zezo alharazi, May 28 '19 at 02:05
Possible duplicate of https://stackoverflow.com/questions/1271562/binary-string-to-integer — Miller Cy Chan, May 28 '19 at 02:57

Lperlind · Answer 1 · 2019-05-28T04:34:11.067

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 '19 at 04:34

answered May 28 '19 at 02:53

Lperlind

1
2

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 – zezo alharazi May 28 '19 at 22:23

shingo · Answer 2 · 2019-05-29T03:22:23.903

0

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 '19 at 03:22

answered May 28 '19 at 03:36

shingo

18,436
5
23
42

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 May 28 '19 at 23:15
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 May 28 '19 at 23:30
StringBuilder sb = new StringBuilder(); while (Decimalvalue > 0) { sb.Insert(0, Decimalvalue % 2); Decimalvalue /= 2; } /// string RevercBinary = sb.ToString(); – zezo alharazi May 28 '19 at 23:31
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. – shingo May 29 '19 at 03:12
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 – zezo alharazi May 29 '19 at 05:53
When convert back, use padleft: `Convert.ToString(5, 2).PadLeft(8, '0');` – shingo May 29 '19 at 06:15
am sorry i don't know how to write the convert back , this time i will have BigInteger not String , can u please write for me the convert back . thanks . lot u help me a lot – zezo alharazi May 29 '19 at 23:27
Plzzzzzzzzzz :( – zezo alharazi May 31 '19 at 20:32

Faster way to convert large binary string to BigInteger

2 Answers2

Linked