1

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.

Pam
  • 474
  • 1
  • 4
  • 13
  • Just use [Array.Reverse()](http://msdn.microsoft.com/en-us/library/system.array.reverse(v=vs.110).aspx). – Robert Harvey Apr 08 '14 at 20:33
  • Thank you Robert. I get I have some problem understanding the inner structure of Biginteger: I have made a lot of attempts all unsuccessful. I am probably still missing to understand it right. – Pam Apr 08 '14 at 20:34
  • 2
    BigInteger expects your `bytes` to contain actual binary values, not bit digits. You'll have to raise each digit to it's proper binary exponent, and then add it to an accumulated result. – Robert Harvey Apr 08 '14 at 20:35
  • hmmm, so maybe a left bit shift is needed for each byte in the loop ? – Pam Apr 08 '14 at 20:42
  • 1
    Yes. I'm just wondering how you're going to do that without overflowing. The easiest way is probably just to create a string from your byte array, and then use BigInteger to parse the string. Make sure you use StringBuilder, not concatenation. – Robert Harvey Apr 08 '14 at 20:44
  • Well, in that case I might just use join(), no ? – Pam Apr 08 '14 at 20:47
  • Your original array is an array of integers, not of strings. You would still have to loop through the elements, calling ToString() on each one. – Robert Harvey Apr 08 '14 at 20:48
  • 1
    I gave you all this good advice, and then realized that I don't know how to parse a binary string to a BigInteger. – Robert Harvey Apr 08 '14 at 21:04
  • Well there should be actually. It's the most natural parsing (??) – Pam Apr 08 '14 at 21:30
  • 1
    There's a Hex parse, but not a binary one. I have methods in my latest project for parsing binary strings to bytes, but not BigIntegers. I have the feeling that most folks don't use binary number much unless they're programmers. – Robert Harvey Apr 08 '14 at 21:31

2 Answers2

3

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.

Community
  • 1
  • 1
Tim S.
  • 55,448
  • 7
  • 96
  • 122
  • Why x > 0? Don't you lose your placeholder zeroes if you do that? – Robert Harvey Apr 08 '14 at 21:00
  • 1
    @RobertHarvey no, I only need to tell between 0 and 1. It's equivalent to `x == 1`, `x != 0`, etc. It's just what I arbitrarily picked. Note that it's `Select`, not `Where` or anything complicated like that - I'm just converting the ints to bools. – Tim S. Apr 08 '14 at 21:01
  • I could arrive to the binary string, reversed. But Biginteger can parse binary strings too ? – Pam Apr 08 '14 at 21:15
  • @Tim solution seems fine. I made some quick tests and it seems all right. Thank you Tim! – Pam Apr 08 '14 at 21:36
  • A last curiosity, if I may. How would be "improve it by building your byte[] using bit shifting" ? – Pam Apr 08 '14 at 21:49
  • 1
    @Pam Phillip's solution has the bit shifting (`<<`) I was thinking of. – Tim S. Apr 08 '14 at 22:21
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
Phillip Trelford
  • 6,513
  • 25
  • 40
  • hmmm, Thank you Phillip, I am trying this one, but the numbers come out wrong. What is byteCount an integer ? – Pam Apr 08 '14 at 21:26
  • 1
    @Pam sorry rushed that a bit, forgot VB.Net has divide sign the other way round for integer division, and the list was in reverse, sample updated – Phillip Trelford Apr 08 '14 at 21:42
  • Ah ok, I get it. No problem, thanks a lot for the interesting solution Phillip. – Pam Apr 08 '14 at 21:46
  • Hi Phillip, I am taking a second look at your solution, as I am thinking it can actually be more general than the other one. Imagine that my list instead of containing a base 2 representation of a number (just 0/1), contained a base 4 representation (values: 0/1/2/3). Could your code be adjusted to handle this case ? And what would be the changes ? Is it enough to change the shifts ? – Pam Apr 09 '14 at 08:45
  • 1
    @Pam it would be possible to change this to handle N bit representations as input, you would need a second for loop inside the current one to iterate over the bits of each item. You'd also need to multiply up `i` by the number of bits in each item, and add the current inner bit index per item, before calculating the respective byte and bit to write to in the target byte array. – Phillip Trelford Apr 09 '14 at 09:27
  • Thank you Phillip. Sounds a bit involved, maybe I will make a specific question, so it can be shared. I am going to need conversions from and to Biginteger from a list (lsb on the left) representing a number in base 4 too. – Pam Apr 09 '14 at 11:11