How to represent a integer by a chain of 8 bit numbers

Question

I am wondering how you can represent an integer as a chain of 8-bit numbers.

That is, (and I don't know how to actually calculate this so the example is wrong, but should demonstrate the basic idea), say you have an integer of arbitrary size, meaning it can be extremely large like Math.pow(100, 100) ≈ 1e+200 or some small number like 1 or 0. You want to be able to compute that number by using a chain of 8-bit values. The question is how to do that.

For example, I can represent 255 like this:

[ 255, 1 ]

That is, our representation has the first value be 8-bits, and then the second value is also 8-bits, and we multiply them together as 255 * 1 = 255. Another case would be 256. We could represent that like this:

[ 255, 1, 1 ]

Meaning (255 * 1) + 1 = 256, but now we don't necessarily know what to add vs. what to multiply. Imagine a large number like 1589158915. I have no idea what it's array of values would be, but say they ended up being like this:

[ 15, 12, 1, 141, 12, 250 ]

And say that from those numbers we could compute the value like this:

15 * 12 + 1 * 141 / 12 - 250

That wouldn't be very ideal, unless perhaps the system also stored the operation with the value, like this:

[ 15, 2, 12, 0, 1, 2, 141, 3, 12, 1, 250 ]

But I have no idea where to begin to figure out how to calculate the number like this, or how to say "given some integer, figure out how to break it apart into some equation that will generate its value". That is the basis of the question. I guess (actually) this would probably be the best approach.

As a sidenote, you can't take the integer 1589158915 and just represent it like this:

[ 1589158914, 1 ] == (1589158914 + 1)

because 1589158915 is not an 8-bit value. This is why it's tricky. In addition, we don't want to do it like this:

[ 255, 255, 255, 255, ... ]
==
255 + 255 + 255 + 255 + ...

Because that would be very inefficient. The solution should be a compact representation.

So the question is, how to take an integer and create an equation from it that will generate its value, where each component of the equation can be represented as an 8-bit integer.

I guess the most straightforward way would be to have 256 digits and powers, like with binary or decimal. So if you have `[x, y, z]`, the value is `x * 256² + y * 256 + z` That way an array of length x can encode 256 to the power of x, or 2 to the power of 8x numbers. — , Nov 21 '18 at 22:14
I was hoping it would be something like that, but I haven't been able to figure out how that is even possible to represent it that way. — Lance, Nov 21 '18 at 22:17
I'm not sure I understand; I just told you it's possible, and how, didn't I? — , Nov 21 '18 at 22:20
I don't know how to write the function to do it. `splitIntoArray(15918591891598) => [x, y, z]` I don't see how to do that. — Lance, Nov 21 '18 at 22:21

score 0 · Accepted Answer · answered Nov 21 '18 at 22:35

0

So, here's the conversion to and from the 256 system:

const To256 = x => {
  var res = [];
  while (x > 0) {
    res.push(x % 256);
    x = Math.floor(x / 256)
  }
  return res;
}

const From256 = x => {
  var res = 0;
  while (x.length) res = 256 * res + x.pop();
  return res;
}

var t = 9483593483;
console.log(t);
t = To256(t);
console.log(t);
t = From256(t);
console.log(t);

Note that the array is in reverse order.

answered Nov 21 '18 at 22:35

Wow, that is neat. I am not sure how anyone figured that out originally, would be interesting to know who first figured this out. – Lance Nov 21 '18 at 22:36
These are just basic conversion algorithms. They'll work for any system if you replace the `256` with the base you want. I did write them from scratch though :) – Nov 21 '18 at 22:38
..... I just found [this](https://stackoverflow.com/questions/53402560/how-to-split-large-integer-into-an-array-of-8-bit-integers) ... how do you go from that question to this one...? As a 30k+ user...? I must be missing something. – Nov 21 '18 at 22:43

score 0 · Answer 2 · answered Nov 21 '18 at 22:46

It sounds like you're essentially describing base-256 arithmetic, although in a kind of circuitous way. Given some list of integers [a, b, c, d] you could compute the number they represent as (parentheses added for clarity):

a*(256**3) + b*(256**2) + c*(256**1) + d*(256**0)

The power to use for the 256 base is determined by the position of the integer in the list. Using this scheme, your example number of 15809158915 could be represented as:

[3, 174, 76, 159, 3]
# 3*256**4 + 174*256**3 + 76*256**2 + 159*256**1 + 3*256**0

This can of course extend to any arbitrarily-sized list. Of course, you could always write out the list of integers in their hexadecimal form instead of base-10:

[0x3, 0xae, 0x4c, 0x9f, 0x03]

Taking things further, you could write the list out as a string with a single 0x prefix to identify the entire string as a hexadecimal number:

0x3ae4c9f03

And voila: you've now duplicated python's hex() function!

>>> hex(15809158915)
'0x3ae4c9f03'

And since python already supports arbitrarily-sized integers, you can represent really, really big numbers this way:

hex(861324987629387561923756912874369128734619287346921367419273)
'0x89378c76db3e9b3e808eea75a42d7ff7d43840e0f41cf43989L'

The "L" at the end of the string indicates that this is a "long" integer, meaning python has engaged its arbitrarily-sized integer support behind the scenes.

In summary, all modern PCs represent numbers internally as a chain of 8-bit integers. 32-bit ints are a chain of 4 8-bit integers, 64-bit ints are a chain of 8 8-bit integers, etc.

If you get a tiny bit fancier, you can represent negative numbers using twos-complement, or floating point numbers using IEEE-754. (Note that I'm ignoring endianness for now.)

How to represent a integer by a chain of 8 bit numbers

2 Answers2