标签: integer-division

我正在 Arduino 上编写一些代码，该代码需要快速运行并对整数百分比进行粗略近似。

例如，给定一个数字，我想找到它的 90%、70% 或 30% 等。最明显的方法是乘以浮点，例如。x * 0.9；或 x * 0.3；但因为我需要速度，所以我想避免浮点计算。如果我只是除以 2 的幂，我会进行按位移位，但是是否有类似的技术可以使用整数来近似 90%、80% 等？

Honeywell DPS8 计算机（和其他计算机）具有“除小数”指令：

该指令将 71 位小数被除数（包括符号）除以 36 位小数除数（包括符号），形成 36 位小数商（包括符号）和 36 位小数余数（包括符号）。余数的 35 对应于被除数的第 70 位。除非余数为零，否则余数符号等于被除数符号。

所以，据我了解，这是整数除法，小数点位于左侧。

  .qqqqq / .ddddd

（我当时在 FORTH 中做过缩放整数数学，但我对这些技术的记忆已经消失在时间的迷雾中。）

要在 DPS8 模拟器中实现此指令，我相信我需要首先创建两个 70 位数字：71 位被除数减去其符号位，36 位除数减去其符号位并向左移动 35 位，以便小数点对齐。

我想我可以用“%”和“/”形成余数和商（在C语言中），但我不确定这些结果是否需要标准化（即移位）。

我找到了“移位和减法”算法“计算机算术” ，幻灯片 10）的示例，但我更喜欢更直接的实现。

我是否走在正确的轨道上，或者解决方案是否更加细致（修复迹象和错误检测已从此处省略；这些阶段都有详细记录。实际的划分是问题所在。）。任何指向此类硬件模拟的 C 实现的指针都会特别有帮助。

我遇到了一个面试问题，尽管我一直在尝试自己解决它，但我认为我需要一些帮助。

我有一个整数数组（正数和负数）表示空间中的点，两点之间的距离定义为abs(A[i]-A[j])，我需要检查该距离是否可以整除给定整数M。

所以情况是这样的：

数组：[-3 -2 1 0 8 7 1]

中号=3

abs(A[1]-A[2]) = 3 （例如，它可以被整数整除）

复杂度应为 O(N+M)，空间为 O(M)

现在这些是问题

1）我知道有一种方法可以考虑所有夫妇，而不使用带有两个“for循环”的明显解决方案，因为复杂性将是N^2，这是不可取的，但我不知道如何做到这一点

2）复杂度 O(N+M) 意味着我需要使用两个 for 循环，但不是一个在另一个循环内？（我的意思是两个单独的 for 循环），我在这里试图理解的是，给定的复杂度是否可以引导我走向我应该使用的最佳算法。

3）当规范中说整数名称为M，复杂度为O(N+M)时，这是否意味着整数M和复杂度存在关系，还是只是名称相同的情况？

4）怎么做？

我希望我已经说得足够清楚了，如果还不够清楚，请告诉我，我会尽力更好地解释自己。

好吧，让我们看看我是否理解正确，这就是我到目前为止正在尝试的：

int testCollection[7];

testCollection[0] = -3;
testCollection[1] = -2;
testCollection[2] = 1;
testCollection[3] = 0;
testCollection[4] = 8;
testCollection[5] = 7;
testCollection[6] = 1;

int arrayCollection[7];

for (unsigned int i = 0; i < 7; i++)
{
    arrayCollection[i] = 1000;
}

for (unsigned int i = 0; i < 7; …

谁能帮我解释一下为什么在这些情况下余数的符号不同？这是模拟器错误还是真实的 CPU 也会这样做？

8 / -3 : quotient(AL) = -2 remainder(AH) =  2
-8 / 3 : quotient(AL) = -2 remainder(AH) = -2

在 intel 指令中，idiv(integer divsion) 表示有符号除法。
我得到了 的结果idiv，但我不太明白结果。

- 例子

0xffff0000 idiv 0xffff1100

- 我的错误预测
据我所知，quotient应该是 0，并且remainder应该是 0xffff0000 并且因为...

0xffff0000 / 0xffff1100 = 0  
0xffff0000 % 0xffff1100 = 0xffff0000  

——然而，结果却是……
之前idiv

eax            0xffff0000            # dividend
esi            0xffff1100            # divisor
edx            0x0                     

后 idiv

eax            0xfffeedcc            # quotient
edx            0x7400   29696        # remainder

- 问题。
结果是我无法预料的价值。
有人可以解释一下签名除法（idiv）吗？

- 附加。 这是有关idiv.
idiv使用 eax 寄存器作为源寄存器。
作为执行的结果，商存于eax，余数存于edx。

我正在尝试找到一种在uint64_t不支持 128 位整数的系统上使用 C 实现 EEA 的方法。问题在于，似乎总是存在某些变量会溢出的情况，从而产生不正确的结果。

我知道它可以用 /signed/ 机器字来完成，并且这里和其他地方有很多答案给出了伪代码。可以用无符号且无溢出来完成吗？或者您是否需要更大的可用整数大小？

我目前正在开发一个类来处理大的无符号整数。但是，我需要不完整的功能，即：

\n
1. bi_uint+=bi_uint- 已经实施。没什么好抱怨的。
\n
2. bi_uint*=std::uint_fast64_t- 已经实施。没什么好抱怨的。
\n
3. bi_uint/=std::uint_fast64_t- 已实现，但工作速度非常慢，还需要两倍宽的类型uint_fast64_t。在测试用例中，除法比乘法慢35倍
\n

接下来，我将给出我的除法实现，它基于一个简单的长除法算法：

#include <climits>\n#include <cstdint>\n#include <limits>\n#include <vector>\n\nclass bi_uint\n{\npublic:\n    using u64_t = std::uint_fast64_t;\n    constexpr static std::size_t u64_bits = CHAR_BIT * sizeof(u64_t);\n    using u128_t = unsigned __int128;\n    static_assert(sizeof(u128_t) >= sizeof(u64_t) * 2);\n\n    //little-endian\n    std::vector<u64_t> data;\n\n    //User should guarantee data.size()>0 and val>0\n    void self_div(const u64_t val)\n    {\n        auto it = data.rbegin();\n\n        if(data.size() == 1) {\n            *it /= val;\n            return;\n        }    \n        \n …

int n_attrs = some_input_from_other_function() // [2..5000]
vector<int> corr_indexes; // size = n_attrs * n_attrs
vector<char> selected; // szie = n_attrs
vector<pair<int,int>> selectedPairs; // size = n_attrs / 2
// vector::reserve everything here
...
// optimize the code below
const int npairs = n_attrs * n_attrs;
selectedPairs.clear();
for (int i = 0; i < npairs; i++) {
    const int x = corr_indexes[i] / n_attrs;
    const int y = corr_indexes[i] % n_attrs;
    if (selected[x] || selected[y]) continue; // fit inside L1 cache …

在 C 语言中，最简单的实现公式是什么int divround(int a, int b) {...}，其中输出为 a/b，并采用银行家四舍五入（四舍五入为偶数）？

例如，divround(3,2)两者divround(5,2)的计算结果均为 2。

我正在编写嵌入式代码，所以我不能依赖库。我希望代码对于 ARM 和 RISC-V 是通用的，所以也不需要汇编。我试图模仿np.around(a/b)NumPy 中的行为（它执行大约一半到偶数），因此我可以准确比较来自 Python 和我的嵌入式应用程序的输出测试向量。

假设我有一个整数result和一个整数数组,让我们说[a,b,c](不是固定的长度).我需要检测是否result=a*i +b*j + c*k,用i,j,k>=0.

如果有可能,我更喜欢C/C#中的解决方案.

PS问题来自预订系统,如果其持续时间是给定持续时间的组合,则可以出售旅行.

谢谢!

例如:如果我们有a = 3,则b = 7而不是rezult 20 = 3*2 + 7*2结果9 = 3*3 + 7*0