k的下一個字典排列，約束'大於或等於g'

我有一個位掩碼k，例如01100011. 我有一個索引j，表示我想要保存的最高有效位在01100011 ==> j = 2中取011。我想通過位操作找到k大於g =（（k >>（k.len-1-j））+ 1）< <（k.len-1-j）的最小字典序排列公式，其中k.len是位掩碼的長度（示例中爲8）。k的下一個字典排列，約束'大於或等於g'

例子，

k = 01100011 
for j = 2 ==> g = 10000000 because k>>(k.len-1-j) is 011 
solution is 10000111 
-------------------------------- 
k = 01100011 
for j = 4 ==> g = 01101000 because k>>(k.len-1-j) is 01100 
solution is 01101001 
-------------------------------- 
k = 01100011 
for j = 7 ==> g = 01100100 because k>>(k.len-1-j) is 01100011 
solution is 01100101

我想知道的公式，如果可能的公式是如何構建一個簡單的解釋。

我發現在http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation 下一個數字k的詞典排列的公式，我正在尋找類似的東西。

如果只使用位運算符而不使用編譯器/架構相關指令（我使用java），但不是必需的，會很好。

來源

2016-05-23 AndrewBloom

如果您告訴我們g的值，以及您的工作示例中的正確答案，這個問題會更清楚。 – samgak

@samgak謝謝，編輯和更正。 – AndrewBloom

下面是基於適應從C到Java的解決掉這個問題的答案：爲「大於或等於」「大於」通過去除第一Calculate the smallest integer with k bits set that is greater than another integer x?

public static int smallestIntGreaterOrEqualToXwithKBitsSet(int x, int k) 
{ 
    while (Integer.bitCount(x) > k) 
    { 
     // Substitute the least-significant group of bits 
     // with single bit to the left of them 
     x |= x-1; 
     ++x; 
    } 

    for (int i = k - Integer.bitCount(x); i != 0; --i) 
    { 
     // Set the lowest non-set bit 
     x |= x+1; 
    } 
    return x; 
}

我已經從改變邏輯增量爲x。

要使用此解決你的問題，你可以通過在你的G作爲第一個參數的值，k的位計數作爲第二個：

public static int nextPerm(int k, int j, int len) 
{ 
    int g = ((k >>(len-1-j))+1)<<(len-1-j); 
    return smallestIntGreaterOrEqualToXwithKBitsSet(g, Integer.bitCount(k)); 
}

測試：

System.out.println(Integer.toBinaryString(nextPerm(0b01100011, 2, 8))); 
System.out.println(Integer.toBinaryString(nextPerm(0b01100011, 4, 8))); 
System.out.println(Integer.toBinaryString(nextPerm(0b01100011, 7, 8)));

輸出：

10000111 
1101001 
1100101

來源

2016-05-24 08:29:34 samgak

k的下一個字典排列，約束'大於或等於g'

回答

相關問題