c++ - 检查二进制数的 13 整除性

Question

如果用户输入从最高有效到最低有效的数字，如何检查二进制数是否可整除 13？

位数可能非常大，因此将其转换为十进制然后检查其可分性是没有意义的。

我以传统的方式接近它。位数的范围高达 10^5，因此在将其转换为十进制时会溢出。

如何解决这个问题？例子：

110010000100100 是 13 的 div

111111111111111 不能被 13 整除

Answer 1

这是一个 O(N) 算法：

从左到右遍历位。每增加一个位置就相当于将当前值乘以 2，然后加上 0 或 1。这在模 13 算术中也是如此。当你到达最后一位时，看看最终的值是否等于 0。如果是，那么原始数字可以被 13 整除。