首页 > 代码库 > POJ 1781 In Danger Joseph环 位运算解法
POJ 1781 In Danger Joseph环 位运算解法
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 <cstdio> 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\n", substraHighBit(xy) << 1 | 1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。