题意就是判断一个整数的二进制表达式里是否有连续两个1. 比如13的二进制是1101那么有两个连续的1而9的二进制是1001, 则没有两个连续的1.
我们知道 我们可以用 x & (-x) 来获取一个整数二进制表示里最右边的那个1. 那么我们就可以写一个循环不停的返回最右边的那个1的值, 并且我们记录了上一个1的值, 这样只要有连续两个1, 那么这两个1的值的关系就是两倍.
C代码看下面, 复杂度是 O(log N) 因为最多需要 log N 次就可以把一个整数的二进制位过一遍.
1 2 3 4 5 6 7 8 9 10 11 12 13 | int inspect_bits(unsigned int number) { int cur, prev = 0; while (number > 0) { cur = number & (-number); if (prev * 2 == cur) { return 1; } number -= cur; prev = cur; } return 0; } |
int inspect_bits(unsigned int number) { int cur, prev = 0; while (number > 0) { cur = number & (-number); if (prev * 2 == cur) { return 1; } number -= cur; prev = cur; } return 0; }
英文: Coding Exercise – Inspect Two Consecutive Bits
GD Star Rating
loading...
本文一共 176 个汉字, 你数一下对不对.loading...
上一篇: 谷歌的扔鸡蛋问题
下一篇: C++编程练习题: 对两单向链表求和
扫描二维码,分享本文到微信朋友圈