建立一個函數可以算出 0 ~ n  的所有 1 的數量，再利用差分的原理把答案算出來

此函數具體來說可以利用 1 在二進位中每一位數出現的週期性來處理

舉例來說

像是 0 ~ 5 共 6 個數字的二進位如下:

000
001
010
011
100
101

可以發現
第一位 (最右) 出現了 3 個週期，每個週期出現 1 次 1 ，所以這裡共出現 3 * 1 + (6 mod 1) = 3
第二位出現了 1 個週期，每個週期出現 2 次 1，除此之外還出現了不到一個週期，但是沒有 1 所以不用算，所以共出現 1 * 2 + (6 mod 2)= 2
第三位出現了 0 個週期，每個週期出現 4 次 1，除此之外還出現了不到一個週期，所以共出現 0 * 4 + (6 mod 4) = 2
這樣 0 ~ 5 出現的 1 的數量就是 3 + 2 + 2 = 7

由於數字最大為 2 的 31 次方，因此每個數字判斷 32 次，每個 query 算兩次，所以 worst case 時間複雜度 32 * 2 = 64 = O(1)

水題