问题标签 [integer-division]

我正在尝试除以整数，但结果为 0。我只是不明白我做错了什么。我在这个例子中只使用了 int，但使用 float 或 double 得到相同的结果测试。

我使用的代码是：

我得到的结果是：

2011-01-09 16:45:53.411 XX[8296:207]问问题：5
2011-01-09 16:45:53.412 XX[8296:207] playerResult: 2
2011-01-09 16:45:53.412 XX[ 8296:207] 错误答案：3
2011-01-09 16:45:53.413 XX[8296:207] 百分比正确：0 %
2011-01-09 16:45:53.414 XX[8296: 207] 百分比错误：0 %
2011-01 -09 16:45:53.414 XX[8296:207] 计算​​：5
2011-01-09 16:45:53.415 XX[8296:207] 错误答案：0 %

我非常感谢帮助:-)

我正在写这段代码：

结果为 0。这是为什么，我该如何解决这个问题？

谁能向我解释这个 MIDP Java 函数是如何工作的？我对正在使用的运算符特别好奇。

非常感谢

我是计算机科学专业的，对汇编语言如何处理整数除法函数感兴趣。似乎简单地将分子相加，同时给出除法和模数，太不切实际了，所以我想出了另一种使用位移、减法和 2 查找表来进行除法的方法。

基本上，该函数取分母，并根据 2 的最高幂生成“块”。因此，除以 15 得到 4 的二进制块，除以 5 得到 3 的二进制块，依此类推。然后生成第一个 2^block- size 分母的倍数。对于每个倍数，将第一个块之后的值写入查找表，以第一个块的值为键。

示例：二进制 5 的倍数 - 块大小 3（八进制）

因此，实际过程包括获取第一个块，在第一个块上进行左位移，并减去块映射到的值。如果结果数为 0，则它是完全可整除的，如果该值变为负数，则不是。

如果您添加另一个枚举查找表，在其中将值映射到计数器，您可以计算除法的结果！

示例：再次是 5 的倍数

然后剩下的就是将每个块映射到计数器表，你就有了答案。
这种方法存在一些问题。

1. 如果答案不是完全可分的，则该函数返回垃圾。
2. 对于高整数值，这将不起作用，因为 5 块大小将在 32 位或 64 位整数的末尾被截断。
3. 它比 C 中的标准除法慢大约 100 倍。
4. 如果分母是除数的一个因素，那么您的块必须映射到多个值，并且您需要更多的表。这可以通过素数分解来解决，但我读过的所有关于简单/快速素数分解的方法都涉及除法，违背了这个目的。

所以我有两个问题：首先，是否已经有类似的算法？我环顾四周，似乎找不到任何类似的东西。其次，实际的汇编语言如何处理整数除法？

抱歉，如果有任何格式错误，这是我第一次发布堆栈溢出。

Why does this always return value 0.0? Also I want to format this into 00.00 format and convert into string?

我正在从 n 个服务器读取文件，并且我希望每个服务器下载文件的 1/n。我认为一些快速整数数学会起作用，但它似乎并不总是有效：

有时对于正确的数字，比如一个 26 字节的文件被 9 个线程划分（我知道这很荒谬，但只是举例），它对我不利。一定会有更好的办法。有任何想法吗？

我正在编写一个 Fixedpoint 类，但遇到了一些障碍......乘法，除法部分，我不知道如何模拟。我对除法运算符进行了非常粗暴的抨击，但我确信这是错误的。这是到目前为止的样子：

我……不是一个很好的程序员，哈哈！

该类的“部分”是 16 位宽（但表示为一个长的 32 位，因为我想在它们被修复之前它需要空间来容纳可能的溢出），“值”也是如此，它是整数部分。当“部分”在其中一个操作中超过 0xFFFF 时，最高 16 位被添加到“值”中，然后该部分被屏蔽，因此只保留最低 16 位。这是在初始化列表中完成的。

我不想问，但如果有人知道我在哪里可以找到这样的文档，甚至只是“技巧”或如何做这两个运算符，我会很高兴的！在数学方面我是个笨蛋，我知道以前有人必须这样做/问过这个问题，但是搜索谷歌一次并没有把我带到应许之地......

我在考虑一个大数除法的算法：用余数除以 bigint C 除以 bigint D，我们知道 C 在基数 b 中的表示，而 D 的形式为 b^k-1。在示例中显示它可能是最容易的。让我们尝试将 C=21979182173 除以 D=999。

• 我们将数字写成三位数：21 979 182 173
• 我们取连续集合的总和（模 999），从左边开始：21 001 183 356
• 我们将 1 添加到我们“超过 999”之前的那些集合：22 001 183 356

实际上，21979182173/999=22001183 和余数 356。

我已经计算了复杂度，如果我没记错的话，算法应该在 O(n) 中工作，n 是基 b 表示中 C 的位数。我还在 C++ 中做了一个非常粗略和未优化的算法版本（仅适用于 b=10），针对 GMP 的通用整数除法算法对其进行了测试，它确实似乎比 GMP 更好。我在任何地方都找不到这样的实现，所以我不得不求助于对一般部门进行测试。

我发现几篇文章讨论了似乎非常相似的问题，但没有一篇文章专注于实际实现，特别是在不同于 2 的基础上。我想这是因为数字在内部存储的方式，尽管提到的算法似乎有用，比如说，b = 10，即使考虑到这一点。我也尝试联系其他人，但同样无济于事。

因此，我的问题是：是否有文章或书籍或其他东西描述了上述算法，可能讨论了实现？如果不是，那么我尝试在 C/C++ 中实现和测试这样的算法是否有意义，或者这个算法在某种程度上是天生不好的？

另外，我不是程序员，虽然我在编程方面相当不错，但我承认我对计算机“内部结构”知之甚少。因此，请原谅我的无知——这篇文章中很可能有一件或多件非常愚蠢的事情。再次抱歉。

非常感谢！

进一步澄清评论/答案中提出的观点：

谢谢大家——因为我不想用同样的东西评论所有很棒的答案和建议，我只想谈谈你们中很多人提到的一点。

我完全清楚，一般来说，在 2^n 基础上工作显然是最有效的做事方式。几乎所有 bigint 库都使用 2^32 或其他。但是，如果（而且，我强调，它只对这个特定的算法有用！）我们将 bigints 实现为以 b 为底的数字数组，该怎么办？当然，我们在这里要求 b 是“合理的”：b=10，最自然的情况，似乎足够合理。我知道考虑到内存和时间，考虑到数字是如何在内部存储的，我知道它或多或少是低效的，但我已经能够，如果我的（基本的和可能有某种缺陷的）测试是正确的，比 GMP 的一般部门更快地产生结果，这将对实现这样的算法有意义。

Ninefingers 注意到在这种情况下我必须使用昂贵的模运算。我希望不会：我可以通过查看 old+new+1 的位数来查看 old+new 是否交叉，例如 999。如果它有 4 位数字，我们就完成了。更重要的是，由于old<999和new<=999，我们知道如果old+new+1有4位（不能多），那么，(old+new)%999等于删除( old+new+1)，我认为我们可以便宜地做到这一点。

当然，我不是在争论这个算法的明显局限性，也不是我声称它不能被改进——它只能除以特定类别的数字，我们必须先验地知道以 b 为基数的被除数的表示。但是，例如，对于 b=10，后者似乎很自然。

现在，假设我们已经实现了我上面概述的 bignums。说以 b 为底的 C=(a_1a_2...a_n) 和 D=b^k-1。该算法（可能会更加优化）会像这样。希望没有太多错别字。

• 如果k>n，我们显然完成了
• 在 C 的开头添加一个零（即 a_0=0）（以防我们尝试将 9999 与 99 相除）
• l=n%k （“常规”整数的 mod - 不应该太贵）
• old=(a_0...a_l) （第一组数字，可能少于 k 位）
• for (i=l+1; i < n; i=i+k) （我们将有 floor(n/k) 次左右的迭代）
  • 新=(a_i...a_(i+k-1))
  • new=new+old （这是 bigint 加法，因此 O(k)）
  • aux=new+1 （再次，bigint 加法 - O(k) - 我不满意）
  • 如果 aux 有超过 k 个数字
    • 删除 aux 的第一个数字
    • old=old+1 (bigint 再次加法)
    • 在开头用零填充旧的，所以它应该有尽可能多的数字
    • (a_(ik)...a_(i-1))=旧（如果 i = l+1，( a_0 ... a_l )=旧）
    • 新=辅助
  • 在开头用零填充新的，所以它应该有尽可能多的数字
  • (a_i...a_(i+k-1)=新
• quot=(a_0...a_(n-k+1))
• rem=新

在那里，感谢您与我讨论这个问题 - 正如我所说，这在我看来确实是一个有趣的“特例”算法，如果没有人看到它有任何致命缺陷，可以尝试实施、测试和讨论。如果这是迄今为止尚未广泛讨论的事情，那就更好了。请让我知道你的想法。对不起，很长的帖子。

此外，还有一些个人评论：

@Ninefingers：我实际上对 GMP 的工作原理、它的作用以及一般的 bigint 除法算法有一些（非常基本的！）知识，所以我能够理解你的大部分论点。我也知道 GMP 是高度优化的，并且在某种程度上为不同的平台定制了自己，所以我当然不会试图“打败它”——这似乎与用尖头棍子攻击坦克一样富有成效。然而，这不是这个算法的想法——它适用于非常特殊的情况（GMP 似乎没有涵盖）。在不相关的说明中，您确定在 O(n) 中完成了一般划分吗？我见过的最多的是M（n）。（如果我理解正确，那在实践中（Schönhage-Strassen 等）可能不会达到 O(n)。如果我是正确的，Fürer 的算法仍然没有达到 O(n)，几乎纯粹是理论上的。）

@Avi Berger：尽管想法相似，但这实际上似乎与“淘汰九点”并不完全相同。但是，如果我没记错的话，上述算法应该一直有效。

我需要在 Java 中对整数进行除法，结果应该是浮点数。

我可以只使用/符号吗？如：

我有一个定点算术类，这是其中的突出部分：

在 GCC 4.4.5 上，以下代码行：

产生错误：

虽然代码中除以常数零 - 对于不等比例，T/S 或 S/T 之一必须为零 - 如果 S%T == 0（并且 S 不为 0），则 S/T 不为零. GCC 似乎做了足够的优化来确定我的一个分支保证被零除，但没有足够的优化来确定该分支保证不会运行。

我可以把#pragma GCC diagnostic ignored "-Wdiv-by-zero"文件扔进去，但这有可能掩盖真正的警告。

处理这种情况的适当方法是什么？（或者我的分析完全错误，我确实有一个真正的运行时除以零？）