有多种方法可以找到相同的方法,我尝试使用按位操作 -
if(((n<<3) - n)%7 == 0 ) {
print "divide by 7";
}
还有其他更有效的方法吗？
我们可以使用以下算法找到数字是3的倍数 -
如果奇数设置位(奇数位置设置的位)和偶数设置位之间的差值是3的倍数,那么数字也是如此.
我们可以将上述算法推广到其他数字吗？
因此,如果您的数字可由硬件支持的整数表示,并且硬件具有除法或模运算,那么您应该使用它们.它比你写的任何东西都简单,而且可能更快.为了与硬件竞争,你必须使用汇编程序并使用比硬件制造商更好的其他更快的指令,并且没有他们可以使用的无证技巧的优势,但你不能.
这个问题变得有趣的地方是涉及任意大整数的地方.Modulo有一些技巧.例如,我可以告诉你100000000010000010000可以被3整除,尽管我的大脑是一个非常慢的数学处理器而不是计算机,因为%模运算符的这些属性:
(a+b+c) % d = ( (a%d) + (b%d) + (c%d) ) %d(n*a) % d = ( (a%d) + (a%d) + (a%d) +... (n times) ) %d = (n*(a%d)) %d现在请注意:
因此,为了判断一个基数为10的数字是否可以被3整除,我们只需对数字求和,看看总和是否可被3整除
现在使用相同的技巧,使用以八进制或base-8表示的大二进制数(在注释中由@hropyatr指出),并使用7的可分性,我们有特殊情况:
8 % 7 = 1
从中我们可以推断出:
(8**N) % 7 = (8 * (8 * ( ... *( 8 * (8%7) % 7 ) % 7 ) ... %7 = 1
为了"快速"测试7的任意大八进制数的可分性,我们需要做的就是将它的八进制数加起来8并尝试将其除以7.
最后,坏消息.
发布的代码:
if ( (n<<3 - n) % 7 ==0 ) ... 对7的可分性不是一个好的考验.
因为它总是得到true任何n(由@Johnathan莱弗勒指出)
n << 3乘以8,并且相等 8n
所以例如6不能被7整除,
但6<<3 = 48和48 - 6 = 42,这是整除7.
如果你的意思是右移if ( (n>>3 - n ) % 7 == 0 )也不起作用.49测试它,49//8是6,6-49是-43,虽然图49是整除7,-43是没有的.
最简单的测试,if (n % 7 ) == 0是你的最佳镜头,直到n溢出硬件,此时你可以找到一个例程来表示八进制的n,并将八进制数字加到模7.