C编程练习题: 判断整数是否有连续两个1

题意就是判断一个整数的二进制表达式里是否有连续两个1. 比如13的二进制是1101那么有两个连续的1而9的二进制是1001, 则没有两个连续的1.

我们知道我们可以用 x & (-x) 来获取一个整数二进制表示里最右边的那个1. 那么我们就可以写一个循环不停的返回最右边的那个1的值, 并且我们记录了上一个1的值, 这样只要有连续两个1, 那么这两个1的值的关系就是两倍.

C代码看下面, 复杂度是 O(log N) 因为最多需要 log N 次就可以把一个整数的二进制位过一遍.

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 个汉字, 你数一下对不对.

C编程练习题: 判断整数是否有连续两个1. (AMP 移动加速版本)
上一篇: 谷歌的扔鸡蛋问题
下一篇: C++编程练习题: 对两单向链表求和

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

29a80869b61482afa983e72df4b1296a C编程练习题: 判断整数是否有连续两个1 ACM题解数据结构与算法程序设计面试

2 条评论

大致

公式太烧脑了, 还是简单粗暴点好.
玩C语言, 不玩位运算怎么行? 32位机最多循环30次.
int inspect_bits(unsigned int number)
{
unsigned int mask = 0x3;
unsigned int i;
for(i=0;i<sizeof(unsigned int) – 2; ++i)
{
if ((number & mask) == mask)
{
return 1;
}
mask = (mask << 1);
}
return 0;
}

- JustYY.com 小赖子的英国生活和资讯
  
  不错. 你这个看起来更简单一些.

相关文章：

2 条评论

评论