Branislav Vajagić

Bitwise operations.

Today, bitwise operations are mostly used when working with registers in low level systems (embedded systems for example) but their application is much wider.

Today, bitwise operations are mostly used when working with registers in low level systems (embedded systems for example) but their application is much wider. They are much harder to understand than decimal operations, since in school and everyday life we learned only how to work in base 10, therefore everyone can tell you how much is 2 + 2, but not everyone can tell how much is 0b0010 + 0b0010. In this post, we will learn this and much more.

What is a bit and a byte

As you probably know by now, computers understand only binary numbers. A binary number is called a bit and it can have one of two states, 0 or 1. Everyday analogy for a bit is a two state light switch, and the switch can be turned on or off.

  BIT VALUE | BIT STATE
  --------- | ---------
  1         | Set.
  0         | Not set.

With only one bit we cannot do much, we can either say that something is set or not set and that’s all. With more then one bit we can do more complex stuff. Sequence of 8 bits is called a byte and that is the convention. Here is the table of corresponding values in hexadecimal, decimal and binary.

  HEXADECIMAL | DECIMAL | BINARY
  ----------- | ------- | ------
  0x0         | 0       | 0b0000
  0x1         | 1       | 0b0001
  0x2         | 2       | 0b0010
  0x3         | 3       | 0b0011
  0x4         | 4       | 0b0100
  0x5         | 5       | 0b0101
  0x6         | 6       | 0b0110
  0x7         | 7       | 0b0111
  0x8         | 8       | 0b1000
  0x9         | 9       | 0b1001
  0xA         | 10      | 0b1010
  0xB         | 11      | 0b1011
  0xC         | 12      | 0b1100
  0xD         | 13      | 0b1101
  0xE         | 14      | 0b1110
  0xE         | 15      | 0b1111

Converting binary to decimal

Every bit in a bit sequence has it own corresponding value in decimal. First let’s look at a 4 bit sequence:

  0b 1 1 1 1
    | | | |_ decimal 1
    | | |___ decimal 2
    | |_____ decimal 4
    |_______ decimal 8

We can get a decimal analogy of a bit sequence by summing up all numbers whoes bit is set (equal to 1). Therefore decimal analogy for 0b1101 is 13 since 8+4+1=13. Now, this is all good and true if we assume that the bit sequence is in MSB (Most Significant Bit first) configuration. This means that the first bit from the left has most significant decimal value. In LSB (Last Significant Bit first) configuration this would not be true. For LSB sequence we should follow this:

  0b 1 1 1 1
    | | | |_ decimal 8
    | | |___ decimal 4
    | |_____ decimal 2
    |_______ decimal 1

You can see that the only difference is that LSB has last significant decimal value on the first bit, looking from left to right. Here are some examples on how to get decimal value of binary numbers in MSB and LSB configuration:

  BINARY | DECIMAL - MSB | DECIMAL - LSB
  ------ | ------------- | -------------
  0b0101 | 1+4 = 5       | 2+8 = 10
  0b1000 | 8 = 8         | 1 = 1
  0b1001 | 1+8 = 9       | 1+8 = 9

Converting a decimal number to binary is the same but the process is in reverse.

Basic operations with binary numbers

    ADDITION

    0b 1 1 0 1
  + 0b 1 0 0 1
    ----------
    1 0 1 1 0
    | | | | |_ 1 + 1 = 2, write 0 and carry 1 to next row
    | | | |___ 0 + 0 + 1 = 1
    | | |_____ 0 + 1 = 1
    | |_______ 1 + 1 = 2, write 0 and carry 1 to next row
    |_________ 0 + 0 + 1 = 1

    0b 0 0 1 1
  + 0b 1 1 1 1
    ----------
    1 0 0 1 0
    | | | | |_ 1 + 1 = 2, write 0 and carry 1 to next row
    | | | |___ 1 + 1 + 1 = 3, write 1 and carry 1 to next row
    | | |_____ 0 + 1 + 1 = 2, write 0 and carry 1 to next row
    | |_______ 0 + 1 + 1 = 2, write 0 and carry 1 to next row
    |_________ 0 + 0 + 1 = 1

To add two numbers we simply add bits one by one, from right to left and write the sum bellow. If you have 2 ones in a column, you write 0 and carry 1 to the next column. If you have 3 ones in a column (2 from the binary numbers and 1 carried), you write 1 and carry 1 to the next row. You can read this tutorial that explains this much better and shows you how binary adder works on hardware level.

    SUBTRACTION

    0b 1 1 0 1
  - 0b 1 0 0 1
    ----------
      0 1 0 0
      | | | |_ 1 - 1 = 0
      | | |___ 0 - 0 = 0
      | |_____ 1 - 0 = 1
      |_______ 1 - 1 = 0

    0b 1 1 0 0
  - 0b 1 0 0 1
    ----------
    0 0 0 1 1
      | | | |_ 0 - 1 = -1, error, borrow 1 from first column that contains 1
      | | |___ 1 - 0 = 1
      | |_____ 0 - 0 = 0
      |_______ 1 - 1 = 0

Subtraction is a little bit tricky to explain in this way, so I recommend you to watch this video to see how it is done on paper and this tutorial if you are interested in how subtraction is implemented on a hardware level.

The next operations are multiplication and division but they can be achieved by using addition and subtraction. To multiply two numbers, for example 5 * 3, we can add 5 to itself 3 times. Division can be converted to a problem of multiplication or subtraction. This two operations will not be covered in this post. Let’s look at specific cases, when multiplication or division is done by number 2.

  DECIMAL 5  = 0b 0 0 1 0 1 = 5 * 1
  DECIMAL 10 = 0b 0 1 0 1 0 = 5 * 2
  DECIMAL 20 = 0b 1 0 1 0 0 = 5 * 4

  DECIMAL 16 = 0b 1 0 0 0 0 = 16 / 1
  DECIMAL 8  = 0b 0 1 0 0 0 = 16 / 2
  DECIMAL 4  = 0b 0 0 1 0 0 = 16 / 4

Can you see the pattern? If we multiply a number by 2, we are actually moving ones, 1 place to the left and if we divide a number by 2 we are moving ones, 1 place to the right. This is called shifting the bits and with this we can get to bitwise operations.

8 bit numbers and bitwise operations

Bitwise operations are code analogy for hardware logic gates, therefore we have the following operations:

  SYMBOL | NAME
  ------ | -----------
  |      | OR
  &      | AND
  ~      | NOT
  ^      | XOR
  <<     | SHIFT LEFT
  >>     | SHIFT RIGHT

With those 6 operations we can do a lot of powerful stuff but first let’s explain them to people who do not have experience with hardware. As we said, shift operations are special case of multiplication by 2 (shift left) and division by 2 (shift right). First four operations can be explained using the truth table:

OR - the result is 1 if one of the input is 1 (IN1 or IN2 is 1).

  IN1 | IN2 | OUT
  --- | --- | ---
  0   | 0   | 0
  0   | 1   | 1
  1   | 0   | 1
  1   | 1   | 1

AND - the result is 1 if all inputs are 1 (IN1 and IN2 is 1).

  IN1 | IN2 | OUT
  --- | --- | ---
  0   | 0   | 0
  0   | 1   | 0
  1   | 0   | 0
  1   | 1   | 1

NOT - the result is inverted input.

  IN | OUT
  -- | ---
  0  | 1
  1  | 0

XOR - the result is 1 if one input is 0 and one input is 1.

  IN1 | IN2 | OUT
  --- | --- | ---
  0   | 0   | 0
  0   | 1   | 1
  1   | 0   | 1
  1   | 1   | 0

Now that we have the basic idea of what those operations are doing let’s do some examples. We have a binary number 0b01101010 and let’s perform all the operations on this number:

    OR
    0 1 1 0 1 0 0 1
  | 0 0 1 1 0 0 0 1
    ---------------
    0 1 1 1 1 0 0 1
    | | | | | | | |_ 1 or 1 is 1
    | | | | | | |___ 0 or 0 is 0
    | | | | | |_____ 0 or 0 is 0
    | | | | |_______ 1 or 0 is 1
    | | | |_________ 0 or 1 is 1
    | | |___________ 1 or 1 is 1
    | |_____________ 1 or 0 is 1
    |_______________ 0 or 0 is 0

    AND
    0 1 1 0 1 0 0 1
  & 0 0 1 1 0 0 0 1
    ---------------
    0 0 1 0 0 0 0 1
    | | | | | | | |_ 1 and 1 is 1
    | | | | | | |___ 0 and 0 is 0
    | | | | | |_____ 0 and 0 is 0
    | | | | |_______ 1 and 0 is 0
    | | | |_________ 0 and 1 is 0
    | | |___________ 1 and 1 is 1
    | |_____________ 1 and 0 is 0
    |_______________ 0 and 0 is 0

    NOT
  ~ 0 1 1 0 1 0 0 1
    ---------------
    1 0 0 1 0 1 1 0
    | | | | | | | |_ 1 not is 0
    | | | | | | |___ 0 not is 1
    | | | | | |_____ 0 not is 1
    | | | | |_______ 1 not is 0
    | | | |_________ 0 not is 1
    | | |___________ 1 not is 0
    | |_____________ 1 not is 0
    |_______________ 0 not is 1

    XOR
    0 1 1 0 1 0 0 1
  ^ 0 0 1 1 0 0 0 1
    ---------------
    0 1 0 1 1 0 0 0
    | | | | | | | |_ 1 xor 1 is 0
    | | | | | | |___ 0 xor 0 is 0
    | | | | | |_____ 0 xor 0 is 0
    | | | | |_______ 1 xor 0 is 1
    | | | |_________ 0 xor 1 is 1
    | | |___________ 1 xor 1 is 0
    | |_____________ 1 xor 0 is 1
    |_______________ 0 xor 0 is 0

    SHIFT LEFT
  <<0 1 1 0 1 0 0 1
    ---------------
    1 1 0 1 0 0 1 0

    SHIFT RIGHT
  >>0 1 1 0 1 0 0 1
    ---------------
    0 0 1 1 0 1 0 0

Real world application

Example 1

You are probably asking yourself, how can this be useful for anything. At the beginning I mentioned that bitwise operations are really useful when working with registers and here I will explain how.

Let’s say that our register, called PORT, can store 8 bit value 0b00000000 and that every bit in the register corresponds to the state of hardware pin on the MCU. This register would look like this:

  PORT: 0b 0 0 0 0 0 0 0 0
          | | | | | | | |_ PIN0
          | | | | | | |___ PIN1
          | | | | | |_____ PIN2
          | | | | |_______ PIN3
          | | | |_________ PIN4
          | | |___________ PIN5
          | |_____________ PIN6
          |_______________ PIN7

Ok, now that we have set some basic rules, let’s start with the example that goes like this: toggle the state of PIN4 in PORT register. This means that if the current state of the PIN4 is 0, change it to 1 and if the current state of the PIN4 is 1, change it to 0. Starting state of the PORT is 0b01100100.

We want to toggle the state of PIN4 bit and leave other bits unmodified. Many people who are not familiar with bitwise operations would implement some sort of if-else statement but this can be done in 1 line of code with XOR operation.

  PORT = PORT ^ 0b00010000;
  // Or short
  PORT ^= 0b00010000;
  // Or even shorter
  PORT ^= 1 << PIN4;

All of those three lines of abstract code are doing the same thing. If you are thinking to yourself, could we have used OR operation, you are right, for this starting state of the PORT register we could have, but let’s see what will happened if we execute XOR twice and OR twice, one time at the starting state and one time at the new state of the PORT register.

  PORT: 0b 01100100 <- start value of PORT
      ^ 0b 00010000
          --------
        0b 01110100 <- first result, new value of PORT
      ^ 0b 00010000
          --------
        0b 01100100 <- same as starting value of PORT


  PORT: 0b 01100100 <- start value of PORT
      | 0b 00010000
          --------
        0b 01110100 <- first result, new value of PORT
      | 0b 00010000
          --------
        0b 01110100 <- same as first result, nothing is changed

Here you can see that OR operation can be used only to set the bit and that XOR can toggle its state. Therefore, for this example we will use XOR. We can create some rules of thumb:

• OR - used to SET the state of the bit/s.
• AND - used to RESET the state of the bit/s.
• XOR - used to TOGGLE the state of the bit/s.

Example 2

We will use the same register PORT from the last example. Toggle the state of the PIN6, set the PIN5 to 0 and set PIN0 to 1.

  // Toggle the PIN6
  PORT ^= 0b01000000; // <=> PORT ^= 1 << PIN6;
  // Set the PIN5 to 0
  PORT &= 0b11011111; // <=> PORT &= ~(1 << PIN5);
  // Set the PIN0 to 1
  PORT |= 0b00000001; // <=> PORT |= 1 << PIN0;

  // In one line
  PORT = (((PORT ^ (1 << PIN6)) & ~(1 << PIN5)) | (1 << PIN0));

In step-by-step, this will look like this:

  PORT: 0b 01100100 <- start value of PORT
      ^ 0b 01000000 <- XOR
          --------
        0b 00100100 <- first result, new value of PORT
      & 0b 11011111 <- AND
          --------
        0b 00000100 <- second result, new value of PORT
      | 0b 00000001 <- OR
          --------
        0b 00000101 <- final value of PORT

If you are not yet completely sure how this works, best advice is to get a pen and paper and try to do all of the operations from the beginning of the post. Doing all three operations in one line might look too complicated and hard to read. That is true, but there are some benefits to doing it this way. If you run every operation as a single command it will take longer to execute (we are talking about micro/nano seconds) and you would be modifying the state of the PORT register three times. Doing this in a single line is faster to execute and you would be modifying the value of PORT register only once.

Example 3

UART communication is used to transfer data between devices (more about UART here). On one device, 8 push buttons are connected. Every 10ms the state of the buttons is sent to the other device that is doing some processing of buttons’ states. This task can be done in many ways. The most obvious way, in abstract code, would be as follows:

  // Read button states to an array
  void read_buttons(bool *button_states);

  int main(void)  {
    bool button_state[8];

    while(1)  {
      read_buttons(button_state);
      // Will be true every 10ms
      if(isTimePassed())  {
        for(unsigned char i = 0; i < 8; i++)  {
          send_packet(button_state[i]);
        }
      }
    }
  }

  void read_buttons(bool *button_states)  {
    button_states[0] = PIN0;
    button_states[1] = PIN1;
    button_states[2] = PIN2;
    button_states[3] = PIN3;
    button_states[4] = PIN4;
    button_states[5] = PIN5;
    button_states[6] = PIN6;
    button_states[7] = PIN7;
  }

In this abstract code, function read_buttons(*) will store the current state of each button in an array, function isTimePassed() will return true every 10ms and function send_packet() will send value of the button over UART. Since UART protocol is using 10-bit packets to transmit the message, as shown in Figure 1, this can be done much faster and all button states can be sent in one packet. In the example above, we are sending one packet for each button.

  // Read button states to a byte
  void read_buttons(unsigned char button_states);

  int main(void)  {
    unsigned char button_states;

    while(1)  {
      read_buttons(button_states);
      if(isTimePassed())  {
        send_packet(button_states);
      }
    }
  }

  void read_buttons(unsigned char *button_states)  {
    *button_states = (PIN0 << 7)
        || (PIN1 << 6)
        || (PIN2 << 5)
        || (PIN3 << 4)
        || (PIN4 << 3)
        || (PIN5 << 2)
        || (PIN6 << 1)
        || PIN7;
  }

This way the state of all 8 buttons is sent in one packet. Of course, this is just a simple example but you can imagine how this can be used in much more complex application.