POJ 1781 In Danger Joseph环 位运算解法

2019-04-14 11:59发布

站内文章 / 模拟电子
12068 0 1376
Joseph环，这次模固定是2.如果不是固定模2，那么一般时间效率是O(n)，但是这次因为固定模2，那么可以利用2的特殊性，把时间效率提高到O(1)。 规律可以看下图：
具体详细解析请看大师Knuth的Concrete mathematics。
补上纯粹利用位运算写的程序： 作者：靖心 http://blog.csdn.net/kenden23/article/details/30232645
int substraHighBit(int y) { int x = y; x = x | (x>>1); x = x | (x>>2); x = x | (x>>4); x = x | (x>>8); x = x | (x>>16); return y & (x >> 1); } #include int main() { int xy, z; char e; while (scanf("%d %c %d", &xy, &e, &z) && xy) { while (z--) xy = (xy << 3) + (xy << 1); printf("%d ", substraHighBit(xy) << 1 | 1); } return 0; }

热门文章