Combine three 32-bit identifiers into one 32-bit identifier?

Question

Given three identifiers, combine them into a single 32-bit value.

It is known, that the first identifier may have (2^8)-1 different values. Analogically, the second (2^8)-1 and the third (2^10)-1. Therefore the total count of identifiers of all kinds will not exceed (2^32)-1.

Example solution could be to have a map:

• key: 32 bits,
• value: 8 (or 10) bits.

The value would begin at 0 and be incremented every time a new identifier is provided.

Can it be done better? (instead of 3 maps) Do you see a problem with this solution?

---

To clarify, the identifier can hold ANY values from the range <0, 2^32). The only information that is given, is that the total number of them will not exceed (2^8)-1 (or 10th).

The identifiers can have the same values (it's completely random). Consider the randomness source memory addresses given by the OS to heap-allocated memory (e.g. using a pointer as an identifier). I realize this might work differently on x64 systems, however, I hope the general's problem solution to be similiar to this specific one.

This means that a simple bit shifting is out of question.

Answer 1

You can get this with bit shifting and unsafe code.

There is an article on SO: What are bitwise shift (bit-shift) operators and how do they work?

Then you can use the whole 32bit range for your three values

---- 8 bits ---- | ---- 8 bits ---- | ---- 10 bits ---- | ---- unused 6 bits ----

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

Answer 2

You could try something like this:-

#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 3

I think you could make use of a Perfect Hash Function. In particular, the link provided in that that article to Pearson Hashing seems to be appropriate. You might even be able to cut-and-paste the included C program the 2nd article except for the fact that its output is a 64-bit number not a 32-bit one. But if you modify it slightly from

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

to

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

You'll have what you need.