/**
* 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
}
}