StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You're starting off with an initial <code>v</code> that initially has n bits in it set.</p> <p>The point of the game is to have 1 less bit to count at each iteration of the loop. That way, we can just count the number of iterations of the loop that were necessary before we got to the point where n = 0 to figure out the value of the initial n.</p> <p>Notice that, if n = 0, then v = 0, and so the loop will stop at this point. But so long as v > 0, we'll run the body of the loop at least once. At each iteration, we end up with a v that has 1 fewer bit set.</p> <p>Here's why. The first property we need is that <code>v && v == v</code>. Now <code>v</code> is a sequence of bits (the exact number of bits depends on your machine / OS), that you can order from most significant to least significant. When you decrement <code>v</code>, we can note the following:</p> <ol> <li>the least significant bit, call it v[k], that is set to 1 will be set to 0;</li> <li>all bits more significant than v[k] will <em>not</em> change when you decrement <code>v</code>.</li> </ol> <p>Therefore, ANDing <code>v</code> with its decrement will preserve all the more significant bits, but set v[k] to 0. And by definition, all bits that are less significant than v[k], ie v[k-1] ... v[0], are already 0 because v[k] is "the least significant bit that is 1". Therefore after ANDing all the less significant bits will remain at 0. The upshot is that <code>v && (v - 1)</code> contains one less bit set to 1 than <code>v</code> has.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload