We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Sure. To understand this, lets look at everything in binary format.
First of all, for any number N to be power of two it must be of the format 100..00 (in binary) i.e. single 1 followed by all 0s. Now, consider the two operations allowed :
1) If N is not a power of 2, reduce the counter by the largest power of 2 less than N : This is equivalent to removing the first 1 until the number N is power of 2. Thus number of such operations would eqaute to count of all 1s before the last 1.
Example : If N=11010, the largest power of 2 less than N would be 10000, reducing N by it we get 1010, which is equivalent to removing first 1.
2) If N is a power of 2, reduce the counter by half of N : This operation is equivalent to removing trailing zeros, or right shift. Number of such operations would be equal to count of all 0s after the final 1.
Combining the above two steps : we need to count "1s before last 1" and "0s after last 1". To bring uniformity in action, we subtract 1 from N, which will flip all the trailing zeros (and also last 1). Now, the only operation required, is to count 1s in the number i.e. to get popcount for (n-1).
Counter game
You are viewing a single comment's thread. Return to all comments →
Sure. To understand this, lets look at everything in binary format.
First of all, for any number N to be power of two it must be of the format 100..00 (in binary) i.e. single 1 followed by all 0s. Now, consider the two operations allowed :
1) If N is not a power of 2, reduce the counter by the largest power of 2 less than N : This is equivalent to removing the first 1 until the number N is power of 2. Thus number of such operations would eqaute to count of all 1s before the last 1.
Example : If N=11010, the largest power of 2 less than N would be 10000, reducing N by it we get 1010, which is equivalent to removing first 1.
2) If N is a power of 2, reduce the counter by half of N : This operation is equivalent to removing trailing zeros, or right shift. Number of such operations would be equal to count of all 0s after the final 1.
Combining the above two steps : we need to count "1s before last 1" and "0s after last 1". To bring uniformity in action, we subtract 1 from N, which will flip all the trailing zeros (and also last 1). Now, the only operation required, is to count 1s in the number i.e. to get popcount for (n-1).