Algorithm for hashing/encoding multiple values into a single integer value

Question

There is this algorithm for "hashing" or encoding multiple values into a single integer, by assigning exponentially increasing numeric value to individual values. This approach was in particular used in Windows DLLs.

A possible use case can be a client application requesting a list of items matching certain status codes from an API.

For example, if we have the following values:

* open
* assigned
* completed
* closed

...we assign a numeric value to each:

* open - 1
* assigned - 2
* completed - 4
* closed - 8

etc. where each following value is 2x the previous.

Encoding

When we need to pass a combination of any of these values, we add up the corresponding numeric values. For example, for "open, assigned" it is 3, for "assigned, completed, closed" it is 14. This covers all of the unique combinations. As we can see, the "encoding" part is very straightforward.

Decoding

To decode the value, the only way I can think of is switch..case statements, like so (pseudocode):

1 = open
2 = assigned
3 = open + assigned
4 = completed
5 = open + completed
6 = assigned + completed
7 = open + assigned + completed
8 = closed
9 = open + closed
10 = assigned + closed
11 = open + assigned + closed
12 = completed + closed
13 = open + completed + closed
14 = assigned + completed + closed
15 = open + assigned + completed + closed

This algorithm obviously works under the following assumptions:

only works when each value is used only once
only works when both sides know the matching numeric values

Questions:

What is a more optimal way/algorithm to "decode" the values instead of the very elaborate switch..case statements?
Is there a name for this algorithm?

Note: the question is tagged with winapi mostly for discoverability. The algorithm is fairly universal.

Remy Lebeau · Accepted Answer · 2020-10-21 18:57:37Z

What you are describing is formally known as a bit mask, where each bit in an integer is assigned a meaning. Bits are assigned numeric values that are powers of 2 in binary (bit0=2⁰=1, bit1=2¹=2, bit2=2²=4, bit3=2³=8, etc).

You can use the OR and AND logical bitwise operators to set/query individual bits in an integer, eg:

const DWORD State_Open = 1;
const DWORD State_Assigned = 2;
const DWORD State_Completed = 4;
const DWORD State_Closed = 8;

void DoSomething(DWORD aStates)
{
  ...

  if (aStates & State_Open)
    // open is present
  else
    // open is not present

  if (aStates & State_Assigned)
    // assigned is present
  else
    // assigned is not present

  if (aStates & State_Completed)
    // completed is present
  else
    // completed is not present

  if (aStates & State_Closed)
    // closed is present
  else
    // closed is not present

  ...
}

DWORD lState = State_Open | State_Assigned | State_Completed | State_Closed;
// whatever combination you need ...
DoSomething(lState);

In Delphi/Pascal, this is better handled using a Set instead, which is internally implemented as a bit mask, eg:

type
  State = (State_Open, State_Assigned, State_Completed, State_Closed);
  States = Set of State;

procedure DoSomething(aStates: States);
begin
  ...

  if State_Open in aStates then
    // open is present
  else
    // open is not present

  if State_Assigned in aStates then
    // assigned is present
  else
    // assigned is not present

  if State_Completed in aStates then
    // completed is present
  else
    // completed is not present

  if State_Closed in aStates then
    // closed is present
  else
    // closed is not present

  ...
end;

var
  lState: States;
begin
  ...
  lState := [State_Open, State_Assigned, State_Completed, State_Closed];
  // whatever combination you need ...
  DoSomething(lState);
  ...
end;

Collectives™ on Stack Overflow

Algorithm for hashing/encoding multiple values into a single integer value

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related