题意就是判断一个整数的二进制表达式里是否有连续两个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
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK