How can I encode a sets of numbers in a single memory word?

Question

I found a post by optimusfrenk suggesting to encode a sets of numbers in a single memory word in order to get the intersection,he said: "For example, you could encode the set {0,2,3,6,7} in the memory word: ...00000011001101."; I can not find anything about this here and on the web.

How do I do that in c?

Thanks

[Bit manipulation in the C programming language](https://en.wikipedia.org/wiki/Bit_manipulation#Bit_manipulation_in_the_C_programming_language) — alk, Oct 06 '18 at 15:19
"*I can not find anything about this*" what **exactly** are you looking for? — alk, Oct 06 '18 at 15:21

score 2 · Answer 1 · answered Oct 06 '18 at 15:11

"[...] encode the set {0,2,3,6,7} in the memory word: ...00000011001101."

Bits

00000011001101
      ||  || |
      ||  || +- 0
      ||  |+--- 2
      ||  +---- 3
      |+------- 6
      +-------- 7

are set.

To set a bit use

value |= (1<<n);

to clear a bit

value &= ~(1<<n);

Poshi · Answer 2 · 2018-10-06T15:22:48.573

0

You can assign a bit to any element in the set. And use bitwise arithmetic to compute derived sets.

Let's say that

elem_0 = 0b1;
elem_2 = 0b10;
elem_3 = 0b100;
elem_6 = 0b1000;
elem_7 = 0b10000;

Now, you can create a set by or-ing the elements.

set1 = elem_0 | elem_3;
set2 = elem_3 | elem_6 | elem_7;

now, you can compute intersection (and):

intersect = set1 & set2; // == 0x100 == elem_3

Or union (or):

union = set1 | set2; // == 0x11101 == elem_0 | elem_3 | elem_6 | elem_7

Complementary sets (negation)... and so on.

edited Oct 06 '18 at 15:22

answered Oct 06 '18 at 15:13

Poshi

5,332
3
15
32

assigning bits with constants starting with `0x`? – iBug Oct 06 '18 at 15:15
Putting aside the wrong C syntax to express bit-values, your encoding scheme is different form the one presented by the OP's question. – alk Oct 06 '18 at 15:17
Yes, the encoding is different just because I tried to generalize. You cannot encode 2018 with the shown schema. And you are right, this is not good C code. I was trying to be educative more than syntax-correct. I should had used pseudo-code. – Poshi Oct 06 '18 at 15:20
Sure you could, as the meaning of the bits is a matter of definition. Just as your answer's definitions are different from the OP's definitions. – alk Oct 06 '18 at 15:22
Well, I like both the answers, but in the second answer, make sense using values that are power of two to make sure that they are single bits, so: 0x1, 0x2, 0x4, 0x8, 0x10 and so on – Mark Oct 08 '18 at 07:45

How can I encode a sets of numbers in a single memory word?

2 Answers2