Conversion of a binary representation stored in a list of integers (little endian) into a Biginteger

Question

I have a list of integers, say L which contains the binary representation of a number. Each integer in the list L can be 0 or 1. The "least significant bit" is on the left (not on the right).

Example: 1000001111 for the (decimal) number 961, or 0111010001 for 558.

I want to convert the list into a Biginteger.

I have tried the following so far:

Dim bytes(L.Count - 1) As Byte
For i As Integer = 0 to L.Count - 1 
    bytes(i) = CByte(L(i))
Next

Dim Value As New BigInteger(bytes)

Return Value

but the result is completely wrong. Can anyone help to make this conversion? c# of vb.net examples are equally perfect.

I have also looked into something like the following taken from a question here:

Buffer.BlockCopy(intArray, 0, byteArray, 0, byteArray.Length);

but still with no success with the Biginteger conversion.

Answer 1

This should work, using a BitArray to help you get the values, and this snippet from Jon Skeet to convert that to a byte[].

int[] ints = new[] { 1,0,0,0,0,0,1,1,1,1 };
// 1,0,0,... becomes true,false,false,... with this Select
BitArray bits = new BitArray(ints.Select(x => x > 0).ToArray());

byte[] bytes = new byte[(bits.Length + 7) / 8];
bits.CopyTo(bytes, 0);

BigInteger bigInt = new BigInteger(bytes); // 961

If performance is critical, you could probably improve it by building your byte[] using bit shifting. But this is decently (IMO) concise, readable, and (I'd expect) fast code as-is.

558 (0,1,1,1,0,1,0,0,0,1) works, too.

Answer 2

Slightly longer imperative bit shifting approach in VB.Net:

Function ToBigInteger(bits As List(Of Byte)) As BigInteger
    Dim byteCount = (bits.Count + 7) >> 3
    Dim bytes(byteCount) As Byte
    For i = 0 To bits.Count - 1
        If bits(i) <> 0 Then
            bytes(i >> 3) = bytes(i >> 3) Or CByte(1 << (i And 7))
        End If
    Next
    Return New BigInteger(bytes)
End Function