Amazon GrayCheck 那道题的时间复杂度讨论

为啥要while循环？(x & (x - 1))不就是在检查是否只有一个1么？？

我觉得是这样：
if(x != 0) return (x & (x - 1)) == 0 ? true :false;
else return false;

xiaoxin213 发表于 2015-2-22 08:17
为啥要while循环？(x & (x - 1))不就是在检查是否只有一个1么？？

我觉得是这样：

据说是因为case过不了才要加个while..我也觉得不需要while啊。。= =

sherry900105 发表于 2015-2-22 08:46
据说是因为case过不了才要加个while..我也觉得不需要while啊。。= =

哪个case？？

xiaoxin213 发表于 2015-2-22 11:46
哪个case？？

不知道啊。。我又没做过oa。。是地里小伙伴说的~

不是text case过不了， x & (x-1) 目的是去除最右边一个1。那个算法的思想是不断去除最右边的1看是否为0，这个算法只有在 答案是正确的时候（是gray code)才会比查遍8位累计1的个数的时间复杂度要少。

Larrylianj 发表于 2015-2-25 13:34
不是text case过不了， x & (x-1) 目的是去除最右边一个1。那个算法的思想是不断去除最右边的1看是否为0， ...

我看题目的意思是只需要check是不是互为格雷码啊。。要是超过一个1不就不是了么。。还用继续check么。。。

楼主 想问问在地里哪里看到答案 能share下帖子吗？多谢啦～～

Larrylianj 发表于 2015-2-25 13:34
不是text case过不了， x & (x-1) 目的是去除最右边一个1。那个算法的思想是不断去除最右边的1看是否为0， ...

但是只有八位，所以还是O(1) ?谢谢！

这题不是O(1)么，循环走8次，然后计算bit也是计算八次，怎么是O（n）呢

话说我怎么觉得用while 循环时， 应该是   
while (res_ox)
36          {
37             if (res_ox & 0x1) count_one++;
38             res_ox = res_ox >> 1;
39          }
这样才是一位一位比较吧？复杂度 O(n), n 是位数，不是数字的太小。