高效地在JavaScript中添加十六进制字符串 [英] Adding hexadecimal strings in JavaScript efficiently

问题描述

在JavaScript中，我有两个包含十六进制数字的变量作为字符串，每个都是。例如：

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

现在我想添加它们（所以结果应该是'c0cb ）。为了让事情变得更容易一些，让我们对此加以一些限制：

• 数字总是由相同的数字组成（即，这些字符串的长度是相同的。）
  
• 如果需要，这些数字前缀为 0 s，所以它会是'001a'，不只是'1a'。

另一方面，有一些限制让事情变得更加困难：

• 这些数字不包含如上例中的四位数字，但是20位数字。因此，您不能简单地将它们转换为十进制，添加它们并将它们转换回来。换句话说：数字对于JavaScript的数字类型来说太大了（这就是为什么这个答案不起作用）。


• 没有允许溢出。如果您添加'ffff'和'0001'，结果应为'0000' ，而不是'10000'。换句话说，所有的计算都必须使用模块来完成。

我现在有一个算法可以解决所有这些问题，但它很冗长，效率不高，一切都很优雅。它的想法是逐字地浏览字符串，将它们转换为十进制，将它们添加，将它们转换回来，记住潜在的溢出，等等。如上所述，它是完美的，但我认为这不是最好的解决方案。

我怎么能更好地解决这个问题？

PS：我需要在Node.js中这样做，所以如果有现成的模块可以做到这一点，我完全可以这么做： - ）

解决方案

在最简单的情况下，您可以一次添加一位数字，并记录进位：

  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 = d>> 4; 
 result =（d& 15）.toString（16）+ result; 
 
 $ / code> 

如果表现存在问题，您可能更愿意处理多个单一数字一次，但事情变得困难，或者你必须硬编码的位数。即使如此，零填充的东西也需要一些工作。这是一个解决方案，它在三个步骤中执行20个十六进制数字，以便没有数字长度超过32位：



 功能板（s，n）{while（s.length< n）s =0+ s;返回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; 
  

根据 jsPerf ，这段代码似乎比上面的代码快三倍，至少在某些浏览器上。

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 :-)

解决方案

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.

这篇关于高效地在JavaScript中添加十六进制字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！