很难理解简单的算法

Question

对不起，这样的具体问题，但在观看Javascript编写的

function c(a) { 
    if (a < 2) return 2; 
    if (a > 4096) return 4096; 
    var b = a & (a - 1); 
    while (b > 0) { 
     a++; 
     b = a & (a - 1) 
    } 
    return a 
} 

下面的算法我就翻过，我不知道有关的声明。 实际上做了什么？我假设它将A分配给B，然后从B中减去1，但是，如果是这种情况，那么B不会达到0（或低于0），导致无限循环？这如何工作？

我问这个，因为我试图调整算法到PHP，但已经打了一堵墙。它在Javascript中完美地工作，所以我确定我不知道发生了什么。这是我在PHP的尝试：

function c($a) { 
    if ($a < 2) return 2; 
    if ($a > 4096) return 4096; 
     $b = $a 
     $b = ($b - 1); 
    while ($b > 0) { 
     $a++; 
     $b = $a; 
     $b -= 1; 
    } 
    return $b; 
} 

我可以清楚地看到为什么它不工作，但我不知道如何改变算法，使其工作。或多或少，我知道我没有适当地调整算法，因为我不明白它是如何在Javascript中工作的。

无论哪种方式，请帮助我！我并不特别想让某人为我解决问题，但向正确的方向提示会非常棒。 。:(

非常感谢

Answer 1

即线清零的a值的最低设置位并将结果分配到b。

例子：

00010100110101111000 

变为：

00010100110101110000 
       ^

它的工作原理的原因是，减去一个翻转所有位直至并包括设置最低显著位。所有其他位保持不变。按位使用并保留所有未更改的位。

00010100110101111000 a 
00010100110101110111 a-1 
00010100110101110000 a & (a-1) 

---

这个循环反复加一a，直至清除的a一个位给零：

b = a & (a - 1); 
while (b > 0) { 
    a++; 
    b = a & (a - 1); 
} 

换句话说，便将a高达2在一个非常最近的电源效率低下的方式！

相关

• Bit Twiddling Hacks - Round up to the next highest power of 2
• What are bitwise shift (bit-shift) operators and how do they work?

Answer 2

那是一个按位运算：

http://en.wikipedia.org/wiki/Bitwise_operation

http://php.net/manual/en/language.operators.bitwise.php

Answer 3

这是一样的。

function c($a) { 
    if ($a < 2) return 2; 
    if ($a > 4096) return 4096; 
    $b = $a & ($a - 1); 
    while ($b > 0) { 
     $a++; 
     $b = $a & ($a - 1); 
    } 
    return $b; 
} 

Answer 4

我认为它返回的2下一个最接近功率为2的&（A-1）的功率返回0

编辑：

我只是检查这在Java中。它返回2.下一个功率当a为6，则返回8.当a为9则返回16.如果a为2，它返回2.

Answer 5

a & (a-1) 

将做逐位和的和（ A-1）

在PHP

$b = $a & ($a-1) 

应该工作了。

Answer 6

a & (a-1); 

这种说法是做位与操作a和a-1之间。 This链接向您解释有关按位操作的信息。在PHP中，您可以使用&运算符进行AND运算。 Here是与PHP相关的链接。