/**
 * This problem was asked by Pivotal.
Write an algorithm that finds the total number of set bits in all integers between 1 and N.
 * */
class Problem_959 {
    /*
    * solution 1: run a loop from 1 to n and sum the count of set bit, Time:O(nlogn)
    * */
    fun countBits(num: Int): Int {
        var result = 0
        for (n in 1..num) {
            result += help(n)
        }
        return result
    }

    private fun help(n_: Int): Int {
        var count = 0
        var n = n_
        while (n > 0) {
            count += n and 1
            n = n shr 1//n/=2
        }
        return count
    }
}