Bit Sets

Bit Sets

You can consider a 32-bit integer to be a “bit set” of 32 distinct bit flags, where all 1s represent a bit flag that is in the set. A bit set is an inherently parallel architecture, even in ordinary sequential C++ code. The basic idea is that a 32-bit unsigned int stores 32 bit flags. Certain actions on the integer as a whole effectively process 32 bits in parallel. For example, it is very fast to check if any bits are set at all by testing whether the whole integer is zero.

In regards to bit sets stored in an integer, the basic set operations can be implemented very efficiently with C++ bitwise operators:

• Bitwise-AND (&) — intersection
• Bitwise-OR (|) — union
• Bitwise-complement (~) — set complement (negated set)
• Bitwise-and-complement (“A&~B”) — set difference (set minus)

In addition, there are a number of fast operations that can be useful for bit sets:

• Integer zero — null set of bits.
• Integer negative-one — full set of all 1s.
• Bitwise “popcount” — set cardinality or number of elements.

Example code with these ideas for 32-bit sets implemented as unsigned integers:

    u != 0         // Test if any bit is set
    u3 = u2 & u1;  // Intersection of sets (Bitwise-AND)
    u3 = u2 | u1;  // Union of sets (Bitwise-OR)
    u3 = u2 ^ u1;  // Toggle bits in sets (Bitwise-XOR)
    u3 = ~u1;      // Set complement or inverse

The total number of bits set out of 32 can be computed fast as a “popcount” operation using intrinsic functions, such as “__popcnt” in Microsoft Visual Studio and “__builtin_popcount” for GCC (there are also versions for 64-bit longs). In x86 architectures, popcount is a single CPU instruction (POPCNT) implemented in hardware, and is therefore very fast.

Note that these C++ macros assume type “unsigned int” with 32 bits, and therefore 32 distinct bit flags in a single integer variable. For more bits, the “unsigned long” type could be used (64-bit), and there is also the “long long” type (128-bit).

The above macros would need to be changed to use type casts to “unsigned long” rather than just “unsigned” for a 64-bit version. For even more bits, a data structure called a “bit vector” can be implemented as an array of unsigned integers, which generalizes the bit set idea.

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++