问将数的各个数字分量相加/求和的最快方法

EN

用二进制和固定宽度的整数对1进行求和有一个很酷的技巧。在每次迭代中，您将每个数字的一半分成两个值，将一个值向下移位，然后相加。第一次迭代，分隔所有其他数字。第二次迭代、成对的数字等等。

假设27是00011011的8位二进制，那么这个过程是...

00010001 + 00000101 = 00010110  <-  every other digit step
00010010 + 00000001 = 00010011  <-  pairs of digits
00000011 + 00000001 = 00000100  <-  quads, giving final result 4

您可以对decimal使用类似的技巧，但它的效率不如简单的循环，除非您有一个直接表示十进制数的快速操作，可以将选定的数字置零并进行数字移位。所以你花12345678美元就可以得到...

02040608 + 01030507 = 03071115  <-  every other digit
00070015 + 00030011 = 00100026  <-  pairs
00000026 + 00000010 = 00000036  <-  quads, final result

因此1+2+3+4+5+6+7+8 = 36，这是正确的，但只有当您的数字表示是固定宽度的小数时，才能有效地执行此操作。它总是需要lg(n)次迭代，其中lg表示以两为底的对数，你向上舍入。

为了对此稍作扩展(基于评论中的讨论)，让我们假装这是正常的，稍微...

如果你计算个位数的加法，实际上比一个简单的循环有更多的工作。这个想法，与计数位的逐位技巧一样，是重新排序这些加法(使用结合性)，然后并行计算尽可能多的加法，使用单个全宽加法来实现两个半宽加法，四个四分之一宽加法等。数字清除和数字移位操作的开销很大，如果您将其实现为循环(计算或查找每一步的数字掩码和移位距离值)，则开销会更大。“循环”可能应该完全展开，这些掩码和移位距离应该作为常量包含在代码中，以避免这种情况。

支持Binary Coded Decimal (BCD)的处理器可以处理此问题。数字掩码和数字移位将使用比特掩码和比特移位来实现，因为每个十进制数字将被编码为4个(或更多)比特，而与其他数字的编码无关。

一个问题是，BCD支持现在非常少见。它曾经在8位和16位时代相当普遍，但据我所知，现在仍然支持它的处理器主要是为了向后兼容。原因包括……

1. 非常早期的处理器不包括硬件乘法和除法。对这些操作的硬件支持意味着现在将二进制转换为十进制更容易、更有效。现在几乎所有的东西都使用二进制，BCD主要是库中的十进制数字表示，但很少有高级语言曾经为硬件BCD提供可移植的支持，所以自从汇编语言不再是大多数开发人员的现实选择时，BCD支持就不再被使用了。
2. 随着数字变得越来越大，即使是压缩的BCD也是相当低效的打包。基数为10^x的数字表示法具有基数为10的最重要的属性，并且很容易解码为十进制。基数1000每三位数只需要10位，而不是12位，因为2^10是1024。这足以表明你得到了32位的额外十进制数字-9位而不是8位-而且你还剩下2位，例如对于符号位。

问题是，为了让这个数字总和算法有价值，您需要使用可能至少32位(8位)的固定宽度小数。这给出了12个操作(6个掩码，3个移位，3个加法)，而不是(完全展开的)简单循环的15个加法。不过，这只是一个边际收益--代码中的其他问题很容易意味着它实际上更慢。

64位(16位十进制数)的效率提升更加明显，因为仍然只有16次操作(8个掩码，4次移位，4次加法)，而不是31次，但找到支持64位BCD操作的处理器的可能性似乎很小。即使你这样做了，你又需要多久一次呢？这似乎不太可能是值得的努力和可移植性的损失。

以下是Haskell中的一些内容：

sumDigits n = 
  if n == 0 
     then 0
     else let a = mod n 10
          in a + sumDigits (div n 10)

哦，但我刚看到你已经这么做了.

(然后还有一个显而易见的事实：

sumDigits n = sum $ map (read . (:[])) . show $ n

)

要获得简短的代码，请尝试以下代码：

int digit_sum(int n){
    if (n<10) return n;
    return n%10 + digit_sum(n/10);
}

或者，用语言来说，

数字小于10，那么数字-If就是数字本身。

-Otherwise，数字和是当前的最后一个数字(也称为N mod10或n%10)，加上该数字左侧所有数字的数字和(n除以10，使用整数除法)。

-This算法也可以推广到任何基数，用中的基数代替10。