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 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.

score 12 · Accepted Answer · edited May 23 '17 at 12:04

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!

Related

Thanks a lot. I understand entirely now. :) – anditpainsme Jul 11 '12 at 07:58 — anditpainsme, Jul 11 '12 at 07:58

score 2 · Answer 2 · answered Jul 11 '12 at 07:40

2

Thats an bitwise operation:

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

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

answered Jul 11 '12 at 07:40

Ron

1,336
12
20

score 2 · Answer 3 · answered Jul 11 '12 at 07:41

2

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

answered Jul 11 '12 at 07:41

xdazz

158,678
38
247
274

user1168577 · Answer 4 · 2012-07-11T07:52:52.747

1

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.

edited Jul 11 '12 at 07:52

answered Jul 11 '12 at 07:41

user1168577

1,863
11
14

Not sure why I got downvoted but please check http://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2 – user1168577 Jul 11 '12 at 07:46
Right answer for the unstated question. :) But yes: the original function is quite ineffective way to get next-higher power of two (clamped by 2 and 4096). – ash108 Jul 11 '12 at 07:52
If you look at your numbers in binary form, you'll notice that they contain two ones. But if you try `15` for example, the expression returns `14`. You accidentally picked numbers for which it works. – Otto Allmendinger Jul 11 '12 at 07:58
Yes, the repeated application of the formula does yield a power of two after a while, but the `a & (a-1)` alone does not. – Otto Allmendinger Jul 11 '12 at 08:04
That is what I meant. function returns next power of 2. – user1168577 Jul 11 '12 at 08:07

score 0 · Answer 5 · answered Jul 11 '12 at 07:42

0

a & (a-1)

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

in php

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

should work, too.

answered Jul 11 '12 at 07:42

DThought

1,340
7
18

score 0 · Answer 6 · answered Jul 11 '12 at 07:55

0

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.

answered Jul 11 '12 at 07:55

Siddiqui

7,662
17
81
129

Trouble understanding simple algorithm

6 Answers6