1
$\begingroup$

I am trying to imagine a way of encoding a BigInt into a bit stream, so that it is literally just a sequence of bits. Then upon decoding this bit stream, you would generate the standard BigInt sort of data structure (array of small integers with a sign). How could you encode the BigInt as a sequence of bits, and how would you decode it? I don't see how to properly perform the bitwise manipulations or how to encode an arbitrary number in bits larger than 32 or 64. If a language is required then I would be doing this in JavaScript.

For instance, this takes bytes and converts it into a single bit stream:

function arrayOfBytesTo32Int(map) {
  return map[0] << 24
    | map[1] << 16
    | map[2] << 8
    | map[3]
}

How would you do that same sort of thing for arbitrarily long bit sequences?

$\endgroup$
2
$\begingroup$

Look at Elias delta or gamma coding as an example.

$\endgroup$
1
  • $\begingroup$ Mind showing how to do it in code? It's a bit abstract. All the examples I see don't use BigInt or anything, just regular ints, (in which case it's useless to do). $\endgroup$ – Lance Pollard Jul 6 '20 at 0:31
2
$\begingroup$

There are many common encodings for arbitrary-length integers. I would say that the most-used representations are:

  • Length-data representations, where the number of bytes/words is written first, followed by the data.
  • A "continuation bit" representation. If the word size is b bits, then an integer is split into groups of b-1 bits, with the high order bit denoting whether there is another byte following or not.

You can mix and match these. The ASN.1 Basic Encoding Rules are a case in point, where in the general case, the length field is encoded in base 128 using the continutation bit. ASN.1 BER is used in many network protocols, such as VoIP, SNMP, and LDAP, as well as in cryptography, where representing large integers is a common thing.

$\endgroup$
1
  • $\begingroup$ Actually in the ASN.1 representation you refer to, it is the value that is encoded in base 128. The length (as a count of base-128 digits, minus 1) is encoded in base 1 and interleaved with the digits. $\endgroup$ – Martin Kochanski Jul 6 '20 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.