劍指-4,7幸運數字

題目:
我們把只包含4或7的數稱為幸運數字.
例如:4,7,44,47,74,77等等是幸運數字,而41,42不是幸運數字.
求從小到大的順序第M個幸運數字.而M的大小是,0 <10^18次冪

思路:
先通過2^k -1 = (M+1) 得到M處於二叉樹的層,
例如:
M=7 , k = log2(7+1)+1 = 4 得到M處於二叉樹的第四層

然後再通過 M - (2^(k-1)-1)得到索引值.
例如: 7 - (2^(4-1)-1) = 7 - 7 = 0 8 - (2^(3)-1) = 8-7 = 1 9 - (2^3 - 1) = 9-7=2

然後因為處在第4層,數是有規律的,只有三位數,最左側是444,最右側是777
將索引轉換為3位的二進制數,碰到一個碰到一個0就追加一個4,碰到一個1就追加一個7

public static void main(String[] args) {
    int m = (int) (Math.pow(2, 6) - 2);
    for (int i = 1; i <= m; i++) {
        printLuckNumber(i);
    }
}

private static void printLuckNumber(int m) {
    int k = (int) Math.ceil(Math.log((double) (m + 2)) / Math.log((double) 2));
    int index = (int) (m - (Math.pow(2, k - 1) - 1));
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < k - 1; i++) {
        sb.append((index & 0x1) == 1 ? '7' : '4');
        index >>>= 1;
    }
    String result = sb.reverse().toString();
    System.out.printf(result + " ");
    if (!result.contains("4")) {
        System.out.println();
    }
}

結果
4 7 
44 47 74 77 
444 447 474 477 744 747 774 777 
4444 4447 4474 4477 4744 4747 4774 4777 7444 7447 7474 7477 7744 7747 7774 7777 
44444 44447 44474 44477 44744 44747 44774 44777 47444 47447 47474 47477 47744 47747 47774 47777 74444 74447 74474 74477 74744 74747 74774 74777 77444 77447 77474 77477 77744 77747 77774 77777