Trouble understanding simple algorithm

Question

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…

Accepted Answer

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

Example:

```
00010100110101111000
```

Becomes :

```
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!

- What are bitwise shift (bit-shift) operators and how do they work?

Trouble understanding simple algorithm

Solution

Problem

Related problems