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

看OA有一道题是判断两个byte是否互为gray code

然后看到了一个帖子有两种答案

一个是while循环那种

另一个就是直接bit运算的

bit运算那种应该是O(1)没错了, while循环那种怎么都觉得不是O(n)啊, 总觉得是logn级别的。。求大牛解释~~

谢谢么么哒~

while循环那种情况是这样的：

int x = (byte)(term1 ^ term2);
while(x != 0){                        
            x = (byte)(x & (x - 1));                        
            count++;               
        }               
        return count == 1 ? 1:0;

个人觉得因为while不是完全遍历了x里面的所有位, 只是挑出了x中的1逐位变为0, 所以总觉得是logn级别的。。应该不是O(n)

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

xjwun 发表于 2015-2-22 05:49
你说的快排吧

但是实际上位运算这种底层运算应该不是String字符串判断那种一位一位比较啊 我觉得位运算的话应该是直接定位到为1的那个位然后变成0 所以应该是直接忽略了所有的0位 这样的话时间复杂度肯定是小于n大于1的 只有可能是log级的。。不知道这么分析对不对。。

sherry900105 发表于 2015-2-22 05:17
while循环那种情况是这样的：

int x = (byte)(term1 ^ term2);

感觉worst还是O(N)吧，

xjwun 发表于 2015-2-22 05:42
感觉worst还是O(N)吧，

你是指所有位都是1的情况么。。但是不能看worst啊。。二分查找worst还是n呢。。。

xjwun 发表于 2015-2-22 05:42
感觉worst还是O(N)吧，

不对不对说错了。。。= =有个排序算法的worst是n。。脑子都乱了。。

sherry900105 发表于 2015-2-22 05:45
不对不对说错了。。。= =有个排序算法的worst是n。。脑子都乱了。。

个人感觉这个code要数所有为1的为，最后判断是不是只有一位为1，所以我觉得不能像二分那样变成logn，因为每次没有什么丢掉一半的情况，我也不知道对不对，期待大牛解答哈

sherry900105 发表于 2015-2-22 05:45
不对不对说错了。。。= =有个排序算法的worst是n。。脑子都乱了。。

你说的快排吧

sherry900105 发表于 2015-2-22 05:17
while循环那种情况是这样的：

int x = (byte)(term1 ^ term2);

不是O(n), 而是O（1）， 因为就只有32bit而已

zengm321 发表于 2015-2-22 07:06
不是O(n), 而是O（1）， 因为就只有32bit而已

那那个while循环的复杂度也只有O1？！