[我正在寻找一种确定大数是否可以被11整除的方法
我的理解:(偶数位置的数字总和-奇数位置的数字总和)%11 == 0 ==> 是
这适用于某些示例。
示例:3816 =>(3 + 1)-(8 + 6)= -10如果是负数,我们是否需要考虑模数百分比为11的-10的2的补数?]
类似地:391679 => 11-24 = -13(此数字也可被11整除)
您能帮我理解吗?预先感谢。
[数字3816和391679不能被11整除。仅用%(模)11验证备用数字总和之间的差异就足以将11除以整数,即使该差异为负。
编译器通常使用[1]或更适合现代处理器[2]的方法对不变除数进行除法运算>
如果除数
:(x)
(即要除以11
的数字)为负数,则取反该值,以便使用正十进制数字。[这是(丑陋的)技巧:给定一个n位非负十进制数字,其位数为x = {d(n - 1), .., d(0)}
,在伪代码中使用交替的add / sub ::
int result = 0, op = 1; for (int i = n; i > 0; i--) { if (op) result += x[i - 1], op = 0; else result -= x[i - 1], op = 1; }
[此时,如果
result
可被11
整除,则(x)
可被11
整除。这里要问的显而易见的问题是:“所以我们还必须除以11
吗?”
No
。给定(n)
位数字,令:n2 = floor((n + 1) / 2)
。预计算查找表:[{- n * n2, .., + n * n2}
,如果可以被11
整除,则将值设置为(1)(true),否则,将其设置为(0)(false)。
请考虑32位无符号整数的范围:{0, .., 4294967295}
。那是(n = 10)
个十进制数字,所以:(n2 = floor((n + 1) / 2) = 5)
。我们需要一个LUT范围:{- 50, + 50}
让我们为16位无符号整数给出一个明确的示例:{0, .., 65535}
,可能带有(n = 5)
十进制数字,(n2 = floor((n + 1) / 2) = 3)
,对于根据{- 15, + 15}
预先计算的LUT:
lut[] = {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1};
这可能是'有趣的',但是在本质上是二进制的平台上使用需要十进制表示形式的技巧总是比其价值更大。最好将其视为一个古玩,我很讨厌我花了与编写此答案一样多的时间。用不变式进行倒数除法将始终优于此方法。使用十进制值的要求也很糟糕。无论如何,您都需要将数字字符串除以10!