北京华为的一道面试题.要求是只使用+-*和移位运算,且不能递减3求得余数.
先在csdn上求,求得以下算法:
没看懂,倒是提示我可以用查表的方法,变成求4的余数.自己探求程序如下:
貌似比网上高人给的算法效率更高,可惜没去证实.
想来不会有更高效的做法了,于是开始这种算法的数学证明,如下:
=(n1+n2+n3+n4+...+nm-1+nm) mod 3
因此对数n每次取二进制最后两位(四进制的最后一位),并加入除去二进制最后两位的余数(相当于右移2位),如此反复,直到只剩最后两位,此两位二进制数与原数n同余于3.
现在研究的是,求任意数的余数的高效算法是什么呢?