相关疑难解决方法(0)

来源我的回答:

这个表达式在C预处理器中是否正确

我有点不在这里,我试图了解这种特殊优化是如何工作的.

正如答案中提到的,gcc将整数除法优化为7:

mov edx, -1840700269
mov eax, edi
imul    edx
lea eax, [rdx+rdi]
sar eax, 2
sar edi, 31
sub eax, edi

其转换为C为:

int32_t divideBySeven(int32_t num) {
    int32_t temp = ((int64_t)num * -015555555555) >> 32;
    temp = (temp + num) >> 2;
    return (temp - (num >> 31));
}

我们来看看第一部分:

int32_t temp = ((int64_t)num * -015555555555) >> 32;

为什么这个号码？

那么,让我们取2 ^ 64并将其除以7,看看弹出的是什么.

2^64 / 7 = 2635249153387078802.28571428571428571429

这看起来像一团糟,如果我们把它转换成八进制怎么办？

0222222222222222222222.22222222222222222222222

这是一个非常漂亮的重复模式,当然这不是巧合.我的意思是我们记得7是0b111,我们知道当我们除以99时,我们倾向于在基数10中得到重复模式.因此,当我们除以7时,我们在基数8中得到重复模式是有道理的.

那么我们的号码在哪里？

(int32_t)-1840700269 是相同的 (uint_32t)2454267027

* 7 …

我必须检查一下,如果给定的数字可以被7整除,这通常只是通过做类似的事情来完成n % 7 == 0,但问题是,给定的数字最多可以有100000000,甚至不适合long long.

另一个限制是,我只有几千字节的可用内存,所以我不能使用数组.

我期待数字在stdin上,输出为1/ 0.

这是一个例子

34123461273648125348912534981264376128345812354821354127346821354982135418235489162345891724592183459321864592158
0

应该可以只使用大约7个整数变量和cin.get().它也应该只使用标准库来完成.