枚舉第1位到第n位的第k位數的最佳方法是什麼？

什麼是最好的方法來枚舉所有的數字1至nkth位設置？枚舉第1位到第n位的第k位數的最佳方法是什麼？

例如：
當n = 12和k = 1，答案將是1, 3, 5, 7, 9, 11。
如果k = 2，答案將是2, 3, 6, 7, 10, 11。

一個平凡的方法是遍歷n並檢查是否kth位設置（通過檢查num & (1 << (k-1))是1或0），但有沒有更好的方式來做到這一點？

來源

2014-10-17 saurav

假設我們有n位，並且位k固定爲1，那麼我們尋找的那些數字看起來就像xxxx1xxxx，所以我們只需要生成所有具有（n-1）位的數字。

例如，如果我們有3個比特，我們希望位2被設置，所以我們只需要產生2 ^（N - 1）= 4個數字，和最終的數字看起來像：X1X

所以這些數字是0（00），1（01），2（10），3（11） - >在第2位加上，我們尋找的最終數字是2（010），3（011），6（110 ），7（111）

僞代碼：

int n = ...//User input 
    int bit = numberOfBitUsed(n) 
    for(int i = 0; i < (1<<bit); i++){ 
     int number = generateNumber(i, k); 
     if(number > n){ 
      break; 
     } 

    }

注意：一些位操作，我們就可以實現generateNumber(int number, int k)與O（1）時間複雜度

int generateNumber(int val, int k){ 
    int half = Integer.MAX_VALUE & ~((1<<k) - 1);//Mask for bit from 31 to k 
    int a = half & val; 
    a <<=1; 
    int b = ((1<<k) - 1) & val; 
    int num = a | b | (1<<k); 
    return num; 
}

來源

2014-10-17 07:40:01

由於您刪除了一位，因此您將工作減半。並增加了一些額外的開銷。不知道這是否實際上更快。 – 2014-10-17 08:28:41

@KarolyHorvath你可能是對的！然而，我們可以生成O（1）中的數字（因爲在我的更新的答案中），所以有機會改進:) – 2014-10-17 09:01:20

這似乎不必要的複雜.. – harold 2014-10-17 09:02:44

如果遞增的數量和應該有從下方k中的部分，以上述k中的一部分的進位，其進位將跨越傳播並離開第k比特0，否則它保持1

因此，所有你需要做的是開關的第k個位回：

x = (x + 1) | (1 << k);

只是循環，直到您已經達到上限，有點像這樣（只是一個例子）

for (int x = 1 << k; x < n; x = (x + 1) | (1 << k)) 
    print(x); // or whatever

來源

2014-10-17 09:04:51 harold

什麼是'x '在你的代碼中？ – 2014-10-17 09:06:37

@PhamTrung現在更清楚了嗎？ – harold 2014-10-17 09:09:25

看起來正確:)這應該比我的+1更好 – 2014-10-17 09:09:28

枚舉第1位到第n位的第k位數的最佳方法是什麼？

回答

相關問題