12

不久前我在一个数学论坛上看到一个问题，一个人正在讨论一遍又一遍地将数字中的数字相加，直到得到一个数字。（即“362”将变为“3+6+2”，然后将变为“11”......然后“11”将变为“1+1”将变为“2”，因此“362”将返回 2......我写了一些很好的代码来得到这个答案并发布它只是被一个用户超越，他建议模9中的任何数字都等于这个“无限数字和”，我检查了它，他是对的......好吧几乎是正确的，如果返回零，您必须用“9”将其关闭，但这是一个非常快速的解决方案......

362 = 3+6+2 = 11 = 1+1 = 2

或者...

362%9 = 2

无论如何，mod9 方法非常适合无限添加数字的总和，直到你只剩下一个数字......但是只做一次呢（即 362 只会返回“11”）......谁能想到快速算法？

4

4 回答 4

7

有一个很酷的技巧可以将二进制中的 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

你可以用小数做一个类似的技巧，但它比简单的循环效率低，除非你有一个十进制数字的直接表示，并通过快速操作将选定的数字归零并进行数字移位。所以对于 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 表示以两个为底的对数，然后向上取整。

为了稍微扩展一下（基于评论中的讨论），让我们假装这是理智的，有点......

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

支持二进制编码十进制 (BCD)的处理器可以处理此问题。数字屏蔽和数字移位将使用位屏蔽和位移来实现，因为每个十进制数字将被编码为 4（或更多）位，与其他数字的编码无关。

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

  1. 非常早期的处理器不包括硬件乘法和除法。对这些操作的硬件支持意味着现在将二进制转换为十进制更加容易和高效。现在几乎所有东西都使用二进制，而 BCD 几乎被遗忘了。

  2. 库中有十进制数字表示，但很少有高级语言曾经为硬件 BCD 提供可移植支持，因此，由于汇编程序不再是大多数开发人员的现实选择，BCD 支持就不再被使用。

  3. 随着数字变大，即使打包的 BCD 打包效率也很低。以 10^x 为底的数字表示具有以 10 为底的最重要的属性，并且很容易被解码为十进制。Base 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 操作的处理器的可能性似乎很小。即使你这样做了，你多久需要一次？似乎不太可能值得付出努力和失去可移植性。

于 2013-02-19T05:52:34.800 回答
1

这是 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

)

于 2013-02-19T05:35:20.530 回答
1

对于短代码，试试这个：

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

或者，用文字来说，

- 如果数字小于十，那么数字总和就是数字本身。

- 否则，数字总和是当前最后一位数字（也称为 n mod10 或 n%10），加上该数字左侧所有内容的数字总和（n 除以 10，使用整数除法）。

- 该算法也可以推广到任何基数，将基数替换为 10。

于 2013-04-04T04:07:10.963 回答
0 
int digit_sum(int n)
Do
    if (n<10) return n;
    Exit do
    else

    n=n%10 + digit_sum(n/10);

Loop
于 2013-04-08T04:35:07.803 回答