Math & Bit Manipulation, Power of X
妖孽的 trick。。
因为 3 不是 2 的整数倍,用二进制的各种 bit manipulation 是没前途的。。
不用循环解的话,要么 log ,要么 mod.
log 的解法是利用了 log 公式,如果不用 log10 的话会因为精度问题出错。(其实这个解法不管怎么说都需要考虑下 numerial analysis 提到过的精度问题。。)
妖孽解法是。。1162261467 = 3^19,是整数中最大的 power of 3,所以如果 n 是 power of 3 的话一定可以整除这个数。
这么干和作弊差不多=。= 对喜欢问这种问题的公司致以深深的鄙视。
一个数如果是 power of four,首先是 power of two.
除此之外,只会有一个 '1' 在固定可能的位置上,所以可以直接写个 mask
01010101010101010101010101010101 = 0x55555555
Last updated