歐文的BLOG

在CodeFight選了一個題目為TotalOnes

題目如下

I hven a positive integer k, calculate the total number of 1s in the binary representations of all the numbers from 1 to k, inclusive.

Example

For k = 5, the output should be
totalOnes(k) = 7.

• 110 = 12 => 1
• 210 = 102 => 1
• 310 = 112 => 2
• 410 = 1002 => 1
• 510 = 1012 => 2

Thus, the answer is 1 + 1 + 2 + 1 + 2 = 7.

Input/Output

• [time limit] 3000ms (java)

• [input] integer k

  Guaranteed constraints:
  0 < k < 231.

• [output] integer64

  The total number of 1s in the binary representations of the numbers from 1 to k, inclusive.

其實這個若用暴力破解法很容易，不過因為測試數字最後會很大，導致運算時間超時，這樣就不會通過了

良心建議，演算法的事情，還是自己想出答案比較爽啊

我的解法概念是

因為binary會有重複性的排練，若可以不用重算已經算過的排列的話，這樣就可以大幅度地加速

利用這個特性，先算出小於k的2^n 到底有多少個BitOnes, 最後再利用k 與 (2^n -1)的差，再加上(2^(n - i) 的方式補齊

聽個很模糊吧，

演算法奉上

package owen.com;

import java.util.HashMap;

public class TotalOnes {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //自己想出的演算法
        System.out.println(totalOnes(30)); // 75
        //暴力破解法
        System.out.println(getNto1(30));
    }

    private static HashMap<Integer, Long> mHashMap = new HashMap();
    static long totalOnes(int k) {
        long sum = 0;

        int n = 0;
        for(int i = 0; i< 32 ;i++){
            if(k >= Math.pow(2, i)){
                n = i;
            }
        }

        sum = BitCountPow1(n-1);

        int tmpI = (int)Math.pow(2, n) -1;

        do{
            n--;
            if(tmpI + (int)Math.pow(2, n) > k){
                continue;
            }

            int offset = k - tmpI;
            tmpI +=  (int)Math.pow(2, n);
            sum += BitCountPow1(n-1) + offset;

        }
        while(n > -1);

        return sum;
    }

    private static long BitCountPow1(int n){
        if(n < 0)
            return 0;

        if(n == 0)
            return 1;
        else
        if(!mHashMap.containsKey(n))
            mHashMap.put(n, (int)Math.pow(2, n) + 2*(BitCountPow1(n-1)));

        return mHashMap.get(n);
    }

    private static long getNhas1(int n){
        long count = 0;
        while(n > 0){
            count ++;
            n=n&(n-1);
        }
        return count;
    }

    private static long getNto1(int n){
        int count = 0;
        while(n>0){
            count+=getNhas1(n--);
        }
        return count;
    }
}

小小概念圖示

以五為例，這邊需要會含有 2^2 所有的一加上 5 的一， 因為都有重複性，所以客倌您有感覺了嗎～！