Search code examples
bit-manipulationcomputer-sciencebitbitwise-operators

Why does bit vector a = [01101001] encode set A = {0, 3, 5, 6}?

I'm reading Computer Systems: A Programmer's Perspective and I don't understand why does bit vector a = [01101001] encode set A = {0, 3, 5, 6}?

I did some googling but haven't find anything useful. I've also tried ChatGPT and this video: https://www.youtube.com/watch?v=SYoJ6gUXZvc. Still, I haven't figured it out... Maybe there are some hidden prereqs in figuring this out, like discrete math?

Solution

  • Encoding is a choice "we" make when translating between the computer and non-computer world.

    For instance, in a project about light, 0 could mean daytime and 1 could mean night time. And it would be a valid encoding of those concepts, in the context of that project.

    In your example, the context is about sets of integers.

    One "natural" encoding is to have each bit of the bitset set if the corresponding index is present in the set. There are then 2, equally natural, "choices" regarding the order.

    One approach is to index the bits as such: [0, 1, 2, 3, 4, 5, 6, 7, ...]. Another is to index them as [7, 6, 5, 4, 3, 2, 1, 0]. Note that if using the second scheme, setting the bits for {0, 3, 5, 6} results in [01101001], your exact data.

    It is purely a choice, although a pretty "natural" one. Depending on the context and the operations one wants to do with the set, a different encoding choice might become better.