0

当我准备一些面试时，我得到了以下信息

count=0;
for(i=1;i<=n;i++)
{
    i=(i)&(i-1);    //line 4
    count++;
}
return count;
//--------

i=21,22 same count. For what other values of i we get same count?

我无法理解第 4 行在做什么。谁能帮助我并给我程序的输出.....

在链接http://placement.freshersworld.com/placement-papers/Mentor-Graphics/Placement-Paper-Aptitude-General-32412中找到上述问题（9）

4

4 回答 4

3

如果 i 是 2 的幂或如果 i 是 0，则 i & (i-1) 返回 0，否则返回非零。

检查时，i 将设置为零，计数递增，然后 i 将再次变为 1，然后变为 0，依此类推。

我不确定这个循环是否会终止。

于 2013-11-04T06:47:44.543 回答
3

警告
第二次查看您的代码后，我必须说，它可能编译得很好，但是您会遇到死锁，我确实认为：

for (i=1;i<=n;++i)
{
    i = (i)&(i-1);
    cont++;
}

会发生什么？i什么时候1：

i = 1&0;//is what line 4 boils down to

i也会如此，0如果循环开始，则n至少为 1，所以循环条件仍然为真：

i<=n => 0 <= n ==> true

Soi增加1( i++)，然后整个事情又开始了。第四行再次计算为：

i = 1&0;//assigns 0 again to i

你又回到了原点。这个程序永远不会终止，它只会一遍又一遍地重复相同的操作......

嗯，&是按位与运算符。它在使用时，如在您的带有 2 个整数的代码段中，它返回“打开”或1在两个数字中设置为的位。用简单的英语：表达式计算为一组新的位，这些位在两个操作数中都设置了。以 2 的时间为例i：

00000010 //2
00000001 // i - 1
--------
00000000

在这种情况下，在这两种情况下都没有设置为1。事实上，这将是所有 2 的幂的事实，因为 2 的幂在二进制中看起来像这样：

00000010
00000100
00001000

2 减 1 的幂如下所示：

00001000//power of 2
00000111

在所有其他情况下，至少有 1 位1在两种情况下都设置为：

00000110
00000101
--------
00000100

简单的。

有关 C 中按位运算符的更完整概述和详细说明，您可以随时参考关于 C 中按位运算符的 wiki

于 2013-11-04T06:57:07.323 回答
1

线

i = i & (i-1)

清除 的最低设置位i。所以像这样的循环

while (i) {
    i = i & (i-1);
    count++; }

计算 中设置的位数i。请注意，这仅在i具有无符号类型时才有效。如果i是有符号且为负数，则会导致未定义的行为。

您提供的链接可能是一个记错的问题（离开了while (i)）询问这样的循环。

注释“i=21,22 same count”暗示 21(10101) 和 22(10110) 具有相同数量的设置位。

我必须承认，当我第一次阅读你的问题时，我实际上认为while(i)循环i=(i)&(i-1); count++;只有在这种情况下才有意义，而且它是一个常见的“技巧问题”习语。

于 2013-11-04T06:49:09.507 回答
0

& 是一个按位与运算符。它的计算如下：

例如：i=8

i & (i-1)  is (1000) AND (0111) results 0000.

如果你运行程序，它会进入无限循环，因为

i=1 and (i) & (i-1) gives 0

每次我变成1

所以，修改代码如下，希望你能得到答案：

for(i=1;i<=n;i++)
{
    count=(i)&(i-1);
    printf(" i= %d  count= %d",i,count);
}

结果如下：

i= 1 count= 0
i= 2  count= 0
i= 3  count= 2
i= 4  count= 0
i= 5  count= 4
i= 6  count= 4
i= 7  count= 6
i= 8  count= 0
i= 9  count= 8
i= 10  count= 8
i= 11  count= 10
i= 12  count= 8
i= 13  count= 12
i= 14  count= 12
i= 15  count= 14
i= 16  count= 0
i= 17  count= 16
i= 18  count= 16
i= 19  count= 18
i= 20  count= 16
i= 21  count= 20
i= 22  count= 20
i= 23  count= 22
i= 24  count= 16
i= 25  count= 24
于 2013-11-04T07:52:53.247 回答