Curious about base36 encoding

Question

I want to base36 encode 128bit hexadecimal number, but 128bit exceeds the range of the largest number supported by c language. So, i can't get the value of 36 numbers by finding the remainder and finding the quotient.

I'm curious about the internal algorithm in base36 that handles such long strings. I am wondering how to express the number that cannot be expressed in the number range of c language. Can you tell me about the algorithm for base36? Or, I would like a book or site for reference.

`128bit exceeds the range of the largest number supported by c language`, no there's no upper limit for any types in the C language, so it's possible for an implementation to have for example 200-bit char or 512-bit long. Most modern 64-bit compilers other than MSVC have a [128-bit type](https://stackoverflow.com/q/16088282/995714). And why tag [tag:c++] when you're asking about C — phuclv, Jan 20 '21 at 13:01
128-bit arithmetic can be done with the methods you learned in elementary school, including long division. Given 128 bits, choose a base to work in such as base 256. Then each 8 bits in the 128 bits is a “digit” in base 256, and a 128-bit number is a 16-digit number in base 256. Then you can divide it by 36 using long division: Take the first “digit” of the dividend. Divide it by 36. Store the quotient as the first digit of the result. To the remainder, append a new digit from the dividend. Divide that by 36. Store the quotient, and repeat with the remainder… — Eric Postpischil, Jan 20 '21 at 13:04
… When there are no more digits in the dividend, the remainder you have is a base-36 digit. It is the last (least significant) digit. Take the digits that were stored from the quotient as a new dividend and repeat. That generates the second-to-last base-36 digit. Repeat to generate 25 base-36 digits. — Eric Postpischil, Jan 20 '21 at 13:08
You have two totally different questions here, which have nothing to do with each other: (1) what is the algorithm for representing a number (any number) in base 36, and (2) how can I work with "big" numbers, bigger than the biggest `int` or `long` or `long long` type my compiler knows about? I think you know the answer to (1). For (2), see [here](https://stackoverflow.com/questions/565150/biginteger-in-c) and [here](https://stackoverflow.com/questions/3340511/what-is-the-simplest-way-of-implementing-bigint-in-c). — Steve Summit, Jan 20 '21 at 13:56

score 2 · Accepted Answer · answered Jan 20 '21 at 13:29

I am wondering how to express the number that cannot be expressed in the number range of c language.

Consider an array of bytes. Those bytes consist of bits. Now, assume that the byte consists of 8 bits. Next, consider an array of 16 bytes. There are a total of 128 bits in that array. You can use the lowest element to represent the first 8 bits of a 128 bit integer, the next element to represent bits 8...15 and so on.

That is how arbitrarily large integers can be represented in C: Using arrays of smaller integers each of the elements representing a high radix digit. In the scheme that I described, the number is represented using a radix of 256. You don't necessarily need to use an array of bytes. Typically, arbitrary precision math uses elements of the CPU word size for efficiency. In case of 32 bit element for example, that would be a radix of 4'294'967'296.

In the base36 encoding, the radix i.e. the base of the represenation is - you may have guessed this - 36. It is a textual representation, so elements of the array are chars. Instead of using all 256 values, this representation only uses 36 of those values; specifically those values that encode the upper case latin letter characters and the arabic numeral characters.

Can you tell me about the algorithm for base36?

There are essentially two steps:

First convert the input data to radix-36.
Next map those digits to text so that the digit 0 maps to the character '0', the digit 10 maps to 'A' and 35 maps to 'Z'. You can iterpolate the mappings that I did not provide.

Curious about base36 encoding

1 Answers1