Hacker News new | ask | show | jobs
by euroclydon 5353 days ago
Seriously, for the number -123, the array [3, 2, 1] has the least significant digit in position zero?

[edit] Ah ha, printed arrays have position zero on the left. I thought it was on the right.

4 comments

That's quite standard. The sign can be taken care of separately if one wishes.

The reason for putting the least significant digit first is that carries accumulate towards the most significant digit in ordinary arithmetic. Thus many of the simplest operations want to work from least significant to most significant digit. A final carry out at the top might add an extra digit to the result. It would be really annoying to work with arrays that had most significant digit first. If you had an extra digit you'd have to shift the entire array one place to accommodate it!

Have you read the explanations? They're pretty sensible: it makes digits "align" correctly, so you can essentially just zip & reduce your digits. Which is what you want to do for many operations. Otherwise you'd have to start by reversing your digits arrays or do weird index computations.

It's rather clever.

The digits look backwards, but by storing the digits with the ones place first, they will line up with other numbers correctly even if they have different lengths.

Aka little endian. http://en.wikipedia.org/wiki/Endianness

That way digits[0] will be the least significant digit for any given BigInteger, and digits[1] will always be the second, and so on.

Rather than digits[2] for -123's least significant digit, and digits[1] for, say, 43's least significant digit.