將三個32位標識符合併爲一個32位標識符？

Question

給定三個標識符，將它們組合成一個32位值。

衆所周知，第一個標識符可能有（2^8）-1個不同的值。類似地，第二個（2^8）-1和第​​三個（2^10）-1。因此，各種標識符的總數不會超過（2^32）-1。

實施例的解決方案可能是有地圖：

• 鍵：32位，
• 值：8（或10）個比特。

該值將從0開始並在每次提供新標識符時遞增。

它可以做得更好嗎？ （而不是3張地圖）您是否看到這個解決方案的問題？

---

爲了澄清，標識符可以保存範圍爲< 0,2^32的任何值。唯一給出的信息是它們的總數不會超過（2^8）-1（或10）。

標識符可以具有相同的值（它是完全隨機的）。考慮操作系統給堆分配內存的隨機源內存地址（例如，使用指針作爲標識符）。我意識到這可能會在x64系統上有所不同，但是，我希望將軍的問題解決方案與這個特定的解決方案類似。

這意味着簡單的位移是不成問題的。

Answer 1

你可以嘗試這樣的事情： -

#include <map> 
#include <iostream> 

class CombinedIdentifier 
{ 
public: 
    CombinedIdentifier (unsigned id1, unsigned id2, unsigned id3) 
    { 
     m_id [0] = id1; 
     m_id [1] = id2; 
     m_id [2] = id3; 
    } 

    // version to throw exception on ID not found 
    static CombinedIdentifier GetIdentifier (unsigned int id) 
    { 
     // search m_store for a value = id 
     // if found, get key and return it 
     // else....throw an exception->id not found 
    } 

    // version to return found/not found instead of throwing an exception 
    static bool GetIdentifier (unsigned int id, CombinedIdentifier &out) 
    { 
     // search m_store for a value = id 
     // if found, get key and save it to 'out' and return true 
     // else....return false 
    } 

    int operator [] (int index) { return m_id [index]; } 

    bool operator < (const CombinedIdentifier &rhs) const 
    { 
     return m_id [0] < rhs.m_id [0] ? true : 
       m_id [1] < rhs.m_id [1] ? true : 
       m_id [2] < rhs.m_id [2]; 
    } 

    bool operator == (const CombinedIdentifier &rhs) const 
    { 
     return m_id [0] == rhs.m_id [0] && 
       m_id [1] == rhs.m_id [1] && 
       m_id [2] == rhs.m_id [2]; 
    } 

    bool operator != (const CombinedIdentifier &rhs) const 
    { 
     return !operator == (rhs); 
    } 

    int GetID() 
    { 
     int 
      id; 

     std::map <CombinedIdentifier, int>::iterator 
      item = m_store.find (*this); 

     if (item == m_store.end()) 
     { 
      id = m_store.size() + 1; 
      m_store [*this] = id; 
     } 
     else 
     { 
      id = item->second; 
     }   

     return id; 
    } 

private: 
    int 
     m_id [3]; 

    static std::map <CombinedIdentifier, int> 
     m_store; 
}; 

std::map <CombinedIdentifier, int> 
    CombinedIdentifier::m_store; 

int main() 
{ 
    CombinedIdentifier 
     id1 (2, 4, 10), 
     id2 (9, 14, 1230), 
     id3 (4, 1, 14560), 
     id4 (9, 14, 1230); 

    std::cout << "id1 = " << id1.GetID() << std::endl; 
    std::cout << "id2 = " << id2.GetID() << std::endl; 
    std::cout << "id3 = " << id3.GetID() << std::endl; 
    std::cout << "id4 = " << id4.GetID() << std::endl; 
} 

Answer 2

你可以通過移位和不安全的代碼來獲得。

有SO上的一篇文章：What are bitwise shift (bit-shift) operators and how do they work?

然後你就可以使用全部32位範圍的三個值

---- 8位---- | ---- 8位---- | ---- 10位---- | ----未使用的6位----

int result = firstValue << (8 + 10 + 6); 
result += secondValue << (10 + 6); 
result += thirdValue << 6; 

Answer 3

我想你可以利用a Perfect Hash Function。特別是，該條中提供的鏈接似乎適用於Pearson Hashing。您甚至可以在第二篇文章中剪切並粘貼包含的C程序，除了它的輸出是64位數字而不是32位數字。但是，如果你從

for (j=0; j<8; j++) { 
    // standard Pearson hash (output is h) 

修改它稍微

for (j=0; j<4; j++) { 
    // standard Pearson hash (output is h) 

你有你需要的東西。