Adding hexadecimal strings in JavaScript efficient

问题:

In JavaScript, I have two variables that contain a hexadecimal number as a string, each. E.g.:

var a = 'a3bc',
    b = '1d0f';

Now I want to add them (so, the result should be 'c0cb'). To make things a little bit easier, let's put some constraints on this:

• The numbers always consist of the same number of digits (i.e., the strings are of same length).
• The numbers are prefixed with 0s if necessary, so it will be '001a', not just '1a'.

On the other side, there are constraints that make things a little bit harder:

• The numbers don't consist of four digits as in the example above, but of 20 digits. Hence you can not simply convert them to decimal, add them, and convert them back. In other words: The numbers are too large for JavaScript's number type (this is why this answer does not work).
• There is no overflow allowed. If you add 'ffff' and '0001', the result shall be '0000', not '10000'. In other words: All calculations must be done using a modulo division.

I currently have an algorithm that solves all this, but it's lengthy, not very efficient and everything but elegant. Its idea is to go through the strings character by character, converting them do decimal, adding them, converting them back, remembering potential overflow, and so on. As said, it works perfectly, but I assume it's not the best solution.

How could I solve this in a better way?

PS: I need to do this in Node.js, so if there is a ready-made module available that does this, I'm perfectly fine with this :-)

回答1:

In the simplest case, you can add one digit at a time, keeping track of carry:

var ndigits = 4, i, carry = 0, d, result = "";
for (i = ndigits - 1; i >= 0; i--) {
  d = parseInt(a[i], 16) + parseInt(b[i], 16) + carry;
  carry = d >> 4;
  result = (d & 15).toString(16) + result;
}

If performance is an issue, you might prefer to handle more than a single digit at a time, but then things become either difficult or you have to hard-code the number of digits. Even then, zero-padding stuff will take some work. Here is a solution which does 20 hex digits in three steps, so that no number is more than 32 bits long:

function pad(s, n) { while (s.length < n) s = "0" + s; return s; }
d = parseInt(a.substr(13), 16) + parseInt(b.substr(13), 16);
result = pad((d & 0xfffffff).toString(16), 7);
d = parseInt(a.substr(6, 7), 16) + parseInt(b.substr(6, 7), 16) + (d >> 28);
result = pad((d & 0xfffffff).toString(16), 7) + result;
d = parseInt(a.substr(0, 6), 16) + parseInt(b.substr(0, 6), 16) + (d >> 28);
result = pad((d & 0xffffff).toString(16), 6) + result;

According to jsPerf, this code seems to be three times faster than the above one, at least on some browsers.

回答2:

Would be nice to see what you have already but you could use and arbitrary arithmetic library like BigNumber.

Javascript

require.config({
    paths: {
        bignumber: 'https://raw.githubusercontent.com/MikeMcl/bignumber.js/master/bignumber.min'
    }
});

require(['bignumber'], function (BigNumber) {
    function sumHex() {
        var args = [].slice.call(arguments),
            length = args.length,
            sum = new BigNumber(0, 16),
            index;

        for (index = 0; index < length; index += 1) {
            sum = sum.plus(args[index], 16).mod('100000000000000000000', 16);
        }

        sum = sum.toString(16);
        while (sum.length < 20) {
            sum = '0' + sum;
        }

        return sum;
    }

    var a = '0000000000000000a3bc',
        b = '00000000000000001d0f';

    console.log(sumHex(a, b));

    a = 'ffffffffffffffffffff';
    b = '00000000000000000001';
    console.log(sumHex(a, b));
});

Output

0000000000000000c0cb
00000000000000000000

On jsFiddle