Lately we needed to put a pair of small integers into a single int
variable.
(Let us gloss over the intricacies of what an int
actually is and just
assume it is 32-bit, shall we?)
Nothing crazy hard but still, it took some trial and error before we got it
right.
So, if anybody needs it or is just curious, here’s the code:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "stdio.h" | |
#include "stdlib.h" | |
#define W 15 // Bit-Width of tuple elements (Up to 15 is fine) | |
const int MASK = (1U << W) - 1; | |
const int MASK2W = (1U << 2*W) - 1; | |
const int m = 1U << (W - 1); | |
/** | |
* @brief Trim n into bit-width W. | |
* @return A two's complmenent, W-bit representation of n. | |
*/ | |
inline int trim(int n) { | |
n = n >= 0 ? abs(n) : ~abs(n) + 1; | |
return n & MASK; | |
} | |
/** | |
* @brief Extend the sign of x | |
* @details see: https://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtend | |
* @param x A two's complement, W-bit representation of an integer | |
* @return an int containing the same integer represented by x | |
*/ | |
inline int signExtend(int x) { | |
return ((x & MASK) ^ m) - m; | |
} | |
/** | |
* @brief Pack x and y into a tuple. | |
*/ | |
int packTuple(int x, int y) { | |
int tup = trim(y) | (trim(x) << W); | |
tup &= MASK2W; | |
return tup; | |
} | |
int getX(int tup) { | |
return signExtend(tup >> W); | |
} | |
int getY(int tup) { | |
return signExtend(tup); | |
} | |
/** | |
* @brief Check that a tuple has been packed correctly | |
* @details [long description] | |
* | |
* @param tup The tuple to check | |
* @param expectedX Expected first element of the tuple | |
* @param expectedY Expected second element of the tuple | |
* @return 1 if tup == (expectedX, expectedY); 0 otherwise | |
*/ | |
int testTuple(int tup, int expectedX, int expectedY) { | |
return (expectedX == getX(tup) && expectedY == getY(tup)); | |
} | |
void printTuple(int tup) { | |
int x = getX(tup); | |
int y = getY(tup); | |
printf("t: %x (x: %i, y:%i)\n", tup, x, y); | |
} | |
/** | |
* @brief Returns the elemwnt-wise sum of two tuples | |
* @return The tuple `(t1.x + t2.x, t1.y + t2.y)` | |
*/ | |
int sum(int t1, int t2) { | |
return packTuple(getX(t1)+getX(t2), getY(t1)+getY(t2)); | |
} | |
/** | |
* @brief Test that everything works | |
* @details This will test that all possible tuples are correctly packed and | |
* unpacked. If something goes wrong, it will print some data about the tuple | |
* that failed to unpack. | |
*/ | |
int main(void) { | |
const int MAXELEM = (1U << (W-1)); | |
for(int x = -MAXELEM+1; x < MAXELEM; ++x) { | |
for(int y = -MAXELEM+1; y < MAXELEM; ++y) { | |
int t = packTuple(x, y); | |
if (!testTuple(t, x, y)) { | |
printf("ERROR x: %i, y: %i\n", x, y); | |
printTuple(t); | |
return 1; | |
} | |
} | |
// printf("%i\n", x); | |
} | |
return 0; | |
} |
The code will test all possible tuples and quit if some unpacking gives an unexpected result.
As further reference, check out the classic page Bit Twiddling Hacks, which contains a lot of efficient algorithms for all kinds of bitwise operations!