有沒有一種聰明的方法來「整頓」一個整數位？

假設我有二進制數字0b00110101。有沒有一種聰明的方法來「整頓」一個整數位？

是否有一組平凡的算術運算會產生0b0000111100110011，其中第一個單詞的每一位重複兩次？

這樣的小函數是否存在重複位3,4或N次？

來源

2013-01-14 Eric

缺少查找表，我想答案是：不。無論是隱式還是顯式，您都需要解壓縮輸入字中的位。 –

@Nate這只是一種編寫二進制數字並將其標記的方法（類似於通常對十六進制數字使用「0x0000」的人。 – Mario

@Nate：這是一個二進制文字，我相信C++支持。 – Eric

看一看這個文件：

https://web.archive.org/web/20140629081102/http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

它描述交織兩個16位的數字，這是相當瑣碎把它擴大到32位數字（此創建一個64位數字）。您只需繼續一個額外週期的模式。像這樣：

static const unsigned long long B[] = { 
    0x5555555555555555, 
    0x3333333333333333, 
    0x0F0F0F0F0F0F0F0F, 
    0x00FF00FF00FF00FF, 
    0x0000FFFF0000FFFF 
}; 
static const unsigned int S[] = {1, 2, 4, 8, 16}; 

unsigned long long x; // x must initially fit inside 32 bits 
unsigned long long z; // z gets the result of x interleaved with itself 

x = (x | (x << S[4])) & B[4]; 
x = (x | (x << S[3])) & B[3]; 
x = (x | (x << S[2])) & B[2]; 
x = (x | (x << S[1])) & B[1]; 
x = (x | (x << S[0])) & B[0]; 

z = x | (x << 1);

來源

2013-01-14 02:06:08 paddy

我忘了回答你的問題的第二部分，關於一式三份等......我相信同樣的事情適用，但在'B'中使用不同的幻數。有一個關於三值Morton數字的問題可能有所幫助：http://stackoverflow.com/questions/1024754/how-to-compute-a-3d-morton-number-interleave-the-bits-of- 3-ints – paddy

這是我懷疑存在的那種解決方案。謝謝！ – Eric

我會製作一張表 - 這可能是最快捷的方式。

你當然可以這樣做：

int doublebits(int x) 
{ 
    int y = 0; 
    int bit = 0; 
    while(x) 
    { 
     if (x & 1) 
      y |= 3 << bit; 
     bit += 2; 
     x >>= 1; 
    } 
    return y; 
}

對於一個8位數字，你會做的最多8班下來，8點轉移到使新號碼的權利。

來源

2013-01-14 00:23:15

我不認爲你需要在循環內部使用if，只需要邏輯移位就可以，或者至少在彙編器中。 –

我寫過，所以它的合理可讀性。如果您想要速度，請使用該功能生成表格。 [我不希望現代編譯器，至少gcc和MS生成一個分支]。 –

'x >> 1'是一個懸而未決的陳述。你的意思是什麼？ – 0x499602D2

好吧，這次我相信已經找到了正確的順序：他們建議生產它

http://oeis.org/search?q=3%2C12%2C15%2C48&sort=&language=&go=Search

一種方法是遞歸：

一個（2N）= 4A（N），一（2n + 1）= 4a（n）+3。

這是不重要的。

來源

2013-01-14 02:01:10 Mihai

展望here，似乎這些技術要麼需要LUTs或循環。因此，我認爲最優雅的方式是在計算之前設置y = x時使用「明顯的方式」（鏈接）。

unsigned short x; // Interleave bits of x and y, so that all of the 
unsigned short y; // bits of x are in the even positions and y in the odd; 
unsigned int z = 0; // z gets the resulting Morton Number. 

x = INPUT_PATTERN; 
y = x; 

for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed... 
{ 
    z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1); 
}

是的，我知道這並不一定是「聰明」的解決方案，在OP詢問，但對方的回答到目前爲止，包括循環/遞歸一樣，所以爲什麼不試一試？

來源

2013-01-14 02:11:26 ysap

有沒有一種聰明的方法來「整頓」一個整數位？

回答

相關問題