Search

O.1 — Bit flags and bit manipulation via std::bitset

On modern computer architectures, the smallest addressable unit of memory is a byte. Since all objects need to have unique memory addresses, this means objects must be at least one byte in size. For most variable types, this is fine. However, for Boolean values, this is a bit wasteful. Boolean types only have two states: true (1), or false (0). This set of states only requires one bit to store. However, if a variable must be at least a byte, and a byte is 8 bits, that means a Boolean is using 1 bit and leaving the other 7 unused.

In the majority of cases, this is fine -- we’re usually not so hard-up for memory that we need to care about 7 wasted bits (we’re better off optimizing for understandability and maintainability). However, in some storage-intensive cases, it can be useful to “pack” 8 individual Boolean values into a single byte for storage efficiency purposes.

Doing these things requires that we can manipulate objects at the bit level. Fortunately, C++ gives us tools to do precisely this. Modifying individual bits within an object is called bit manipulation.

Bit manipulation is also useful in encryption and compression algorithms.

Author's note

This entire chapter is optional reading. Feel free to skip it and come back later.

Bit flags

Up to this point, we’ve used variables to hold single values:

However, instead of viewing objects as holding a single value, we can instead view them as a collection of individual bits. When individual bits of an object are used as Boolean values, the bits are called bit flags.

As an aside...

In computing, a flag is a value that acts as a signal for some function or process. Analogously, in real life, a mailbox flag is used to signal that there is something inside the mailbox, so the mailbox doesn’t have to be opened to check.

To define a set of bit flags, we’ll typically use an unsigned integer of the appropriate size (8 bits, 16 bits, 32 bits, etc… depending on how many flags we have), or std::bitset.

Best practice

Bit manipulation is one of the few times when you should unambiguously use unsigned integers (or std::bitset).

In this lesson, we’ll show how to do bit manipulation the easy way, via std::bitset. In the next set of lessons, we’ll explore how to do it the more difficult but versatile way.

Bit numbering and bit positions

Given a sequence of bits, we typically number the bits from right to left, starting with 0 (not 1). Each number denotes a bit position.

76543210  Bit position
00000101  Bit sequence

Given the bit sequence 0000 0101, the bits that are in position 0 and 2 have value 1, and the other bits have value 0.

Manipulating bits via std::bitset

In lesson 4.12 -- Literals we already showed how to use a std::bitset to print values in binary. However, this isn’t the only useful thing std::bitset can do.

std::bitset provides 4 key functions that are useful for doing bit manipulation:

  • test() allows us to query whether a bit is a 0 or 1
  • set() allows us to turn a bit on (this will do nothing if the bit is already on)
  • reset() allows us to turn a bit off (this will do nothing if the bit is already off)
  • flip() allows us to flip a bit value from a 0 to a 1 or vice versa

Each of these functions takes the position of the bit we want to operate on as their only argument.

Here’s an example:

This prints:

All the bits: 00001101
Bit 3 has value: 1
Bit 4 has value: 0

What if we want to get or set multiple bits at once

std::bitset doesn’t make this easy. In order to do this, or if we want to use unsigned integer bit flags instead of std::bitset, we need to turn to more traditional methods. We’ll cover these in the next couple of lessons.


O.2 -- Bitwise operators
Index
5.x -- Chapter 5 summary and quiz

31 comments to O.1 — Bit flags and bit manipulation via std::bitset

  • Cliff

    Thank you for this great material. It's exactly the kind of thing I need for work.

  • Okay, so i understand that bits compose of 8 digits that are 0 and 1 and together they form a byte which consisst of 8 bits.  So, each byte is 8 bits.  So, my question is; is the 8 bits, 16 bits, 32 bits, 64 bits are just a combination of bytes together? for instance, 8 bits is equivalent to 1 byte, 16 bits is equivalent to 2 bytes, 32 bits is equivalent to 4 bytes, and so on...? If that is the case, why not just phrase it bytes intead of bits?

    Second question regarding bit minpulation.  In what situation will you need to manipulate a bits?

  • Chayim

    What is position 3 from the left or right? Either way it’s or 0010 0101 or remains as it is 0000 0101. How is 1101 the 3rd position?
    Answer: counting starts by 0 not 1 so 0000 1101 is the 3rd position.
    Position starts from the right because numbers are added to the left,

  • Tony

    "Bit numbering and bit positions

    Given a sequence of bits, we typically number the bits from right to left, starting with 0 (not 1). Each number denotes a bit position.

    76543210  Bit position
    00000101  Bit sequence
    Given the bit sequence 0000 0101, the bits that are in position 0 and 2 have value 1, and the other bits have value 0."

    I don't seem to understand this part. What is "Bit position"? What does it mean? Why do we have to know the bit sequence? Thanks again!

    • nascardriver

      "Bit position" is the position of the bit. The rightmost bit has position 0, the leftmost bit in this example has position 7.

  • Cerezas

    I think:
    "Each of these functions takes a bit-position argument indicating which bit position we want operated on."

    Should be:
    "Each of these functions takes a bit-position argument indicating which bit position we want to operate at."

    It still feels weird to me, I would say:
    "Each of these functions takes the position of the bit we want to operate on as their only argument."

  • bissetriz

    "However, for Boolean values, this is a bit wasteful"
    You meant almost a *byte* wasteful?

  • Al

    Excuse me, but haven't you realized that using single quotes as numerical separators is completely defeating the purpose of syntax highlighting in all the examples where you do so? Instead of increasing the code's readability, it's doing the opposite.

    I'm not criticizing, just noting something you might have missed.

    • nascardriver

      We're aware of this issue and are looking for a new syntax highlighter. Your local code editor should work with single quote separators.

    • nascardriver

      I've fixed the syntax highlighting for the number separator, it should be colored properly now. If you see that it's not working somewhere, please let me know :)

  • Raul Laasner

    The word "are" is missing in the sentence "Given the bit sequence 0000 0101, the bits that in position 0 and 2 have value 1, and the other bits have value 0."

  • V

    I think the final code example before the end has an accidental single-quote character in it, which causes the color to go all crazy.

    • nascardriver

      The single quote is supposed to be there. C++ has single quotes in integer literals as separators, very useful for binary literals. The problem is the syntax highlighter, which can't handle the separator. We're looking for a new highlighter.

  • HolzstockG

    As I understand when we set as above written "std::bitset<4> test", then for this variable is allocated an entire byte, but we are using only 4 bits of it right?

  • Wolfma

    In the code example in the section "Manipulating bits via std::bitset" list initialization should be used to be in line with the rest of this great tutorial. Keep up the great work!

    to

  • koe

    "a variable must be at least a byte"

    I have wondered about this. Surely a Boolean occupies more than one byte in memory, because there is type and ID information also. Doesn't consolidating 8 Booleans into one std::bitset<8> reduce more than 7 bytes?

  • Parsa

    What if we wanted to flip all of the bits? Loop?

Leave a Comment

Put all code inside code tags: [code]your code here[/code]