sorry for such a specific question but upon looking at the following algorithm written in 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
}

I came accross a statement I wasn't sure about. What exactly does var b = a & (a - 1); actually do? I was under the assumption it assigned A to B and then subtracted 1 from B, however, if that was the case then wouldn't B never reach 0 (or below 0) resulting in an infinite loop? How can this work?

I ask this because I have attempted to adapt the algorithm to PHP but have hit a wall. It works flawlessly in Javascript, so I know for certain that I'm not understanding what is happening. Here is my attempt in 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;
}

I can see clearly why it doesn't work but I'm not sure how to change the algorithm to make it work. More or less, I know that I am not adapting the algorithm properly because I don't understand how it works in Javascript.

Either way, please help me! I don't specifically want someone to work out my problem for me but a hint in the right direction would be really great. :(

Thanks alot.

sorry for such a specific question but upon looking at the following algorithm written in 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
}

I came accross a statement I wasn't sure about. What exactly does var b = a & (a - 1); actually do? I was under the assumption it assigned A to B and then subtracted 1 from B, however, if that was the case then wouldn't B never reach 0 (or below 0) resulting in an infinite loop? How can this work?

I ask this because I have attempted to adapt the algorithm to PHP but have hit a wall. It works flawlessly in Javascript, so I know for certain that I'm not understanding what is happening. Here is my attempt in 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;
}

I can see clearly why it doesn't work but I'm not sure how to change the algorithm to make it work. More or less, I know that I am not adapting the algorithm properly because I don't understand how it works in Javascript.

Either way, please help me! I don't specifically want someone to work out my problem for me but a hint in the right direction would be really great. :(

Thanks alot.

• php
• javascript
• algorithm
• infinite-loop

6 Answers 6

That line clears the lowest set bit in the value of a and assigns the result to b.

Example:

00010100110101111000

Bees :

00010100110101110000
                ^

The reason it works is that subtracting one flips all the bits up to and including the least significant bit that was set. All other bits remain unchanged. Using bitwise-and keeps all the bits that have not changed.

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

This loop repeatedly adds one to a until clearing one bit of a gives zero:

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

In other words, it rounds a up to the nearest power of 2 in a very inefficient way!

Related

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

Thats an bitwise operation:

http://en.wikipedia/wiki/Bitwise_operation

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

It is the same.

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;
}

I think it returns closest next power of 2. For a power of 2 a & (a-1) returns 0.

Edit:

I just checked this in Java. It does return the next power of 2. When a is 6, it returns 8. When a is 9 it returns 16. If a is 2 it returns 2.

a & (a-1)

will do a bitwise and of a and (a-1)

in php

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

should work, too.

a & (a-1);

This statement is doing bit-wise AND operation between a and a-1. This link explain you about Bit-wise operations. In PHP you can use & operator for AND operation. Here is the link related to PHP.