2013-03-07 32 views
1

定義向32位整數的2位或更少的改變被認爲是「有效的」。
爲了簡化,我們來看一個4位二進制的情況。
0000 - > 1000是有效
0000 - > 1100是有效
0000 - > 1001是有效
0000 - > 1101是無效的如何生成朝向二進制整數的所有有效位更改的組合?

因此,實際上,這意味着有C(32,2)* 2^2個可能的組合

我想知道如何編寫一個函數,如vector<int> foo(int numberToBeChanged, int n)需要n(允許位更改的數量)並返回所有可能組合的集合?謝謝。

+0

你真正需要的可能變化的名單(從00000000我想)或檢查給定數目是否在允許的變化(從00000000)的函數: 這裏是根據描述的變化修改後的代碼? – 2013-03-07 08:43:09

+0

如果你只是需要一個函數來計算[兩個二進制字符串的漢明距離](http://en.wikipedia.org/wiki/Hamming_distance#Special_properties),而你是一個現代的X86處理器,你可能想看看在[POPCNT](http://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT)指令(與異或) – 2013-03-07 08:47:07

+0

關於可能的組合數,實際上它不是C(32,2)* 4注意到,因爲你也計算了重複。組合的實數將是1 + 32 + C(32,2),這3個部分中的每一個分別表示沒有變化,1位變化和2位變化的組合。 – aram90 2013-03-07 10:38:42

回答

1

這將做到這一點:

#include <iostream> 
#include <vector> 
using namespace std; 

vector<unsigned int> foo(unsigned int n) 
{ 
    vector<unsigned int> ans; 

    // One of the combinations is not to change anything, i.e. number itself 
    ans.push_back(n); 

    for(unsigned int i = 0; i < 32; i++) { 
     // Combinations with only one bit changed 
     ans.push_back(n^(1 << i)); 
     for(unsigned int j = 0; j < i; j++) { 
      // Combinations with two bits changed 
      ans.push_back(n^(1 << i)^(1 << j)); 
     } 
    } 
    return ans; 
} 

int main() 
{ 
    vector<unsigned int> v = foo(0); 
    for(unsigned int i = 0; i < v.size(); i++) { 
     cout << v[i] << endl; 
    } 
    return 0; 
} 

附:

#include <iostream> 
#include <vector> 
using namespace std; 

/* 
    start denotes bit number from which we should start loop, i.e. we can't 
    modify any bits before that bit to avoid duplicates (we are modifying bits 
    with order from lowest to highest, so if we have modified some bit, next bit 
    to modify should be a higher one. 
*/ 
void foo(vector<unsigned int>& ans, unsigned int number, int n, unsigned int start) 
{ 
    // As we reached to current number someway then it is one of the combinations 
    ans.push_back(number); 
    if(n < 1) { 
     // No more changes allowed, go back 
     return; 
    } 

    // Try change one bit 
    for(unsigned int i = start; i < 32; i++) { 
     foo(ans, number^(1 << i), n - 1, i + 1); 
    } 
} 

int main() 
{ 
    vector<unsigned int> v; 
    unsigned int startingNumber = 0; 
    int changesAllowed = 2; 
    foo(v, startingNumber, changesAllowed, 0); 
    for(unsigned int i = 0; i < v.size(); i++) { 
     cout << v[i] << endl; 
    } 
    return 0; 
} 
+0

嗨aram90感謝您輸入您的答案。但是n實際上表示允許的位更改數量。請檢查我的編輯。我知道這個觀點有誤導性。對於那個很抱歉。 – NSF 2013-03-07 18:56:11

+0

我已根據您的描述更改添加了新代碼。 – aram90 2013-03-08 10:19:36

+0

是的我想通了以後如何做。我沒有使用'number'參數,而是添加一行來檢查是否設置了一位。如果它然後中斷。不管怎麼說,還是要謝謝你! – NSF 2013-03-08 17:48:29

0

如果你想改變在你數N只有兩個位,您可以使用此:

for (size_t i = 0; i < sizeof(int); ++i) { 
    int one = N^(1<<i); 
    for (size_t j = 0; j < i; ++j) 
     vec.push(one^(1<<j)); 
    vec.push(one); 
} 
vec.push(N); 

對於任何其他N:生成的數字帶有n的列表,(N-1),.. 。0位設置,並與你所有的N進行異或。有很多回答的問題,如何生成這樣的列表。 實際上,對於大n,O(2 ^(sizeof(int)))可能的數字。如果我只是想迭代它們,我寧願使用生成器,而不是完整的列表。