In last week’s post, we discussed the boolean and, or, and negation operators and how they are used to alter the control of flow in programs. This week’s topic introduces the boolean operations to manipulate the individual bits of a variable.

Bit Manipulation

This is where a lot of people get confused; how can you take a value and arbitrarily change certain bits? Doesn’t that violate some immutable rule of nature? Nuh-uh, only in math. The dividing line between data and information (a higher meaning given to the data) is arbitrary in computers. We are going to take data, like C integers, and treat them as a group of bits.

Computers have instructions to do the boolean operations on binary data, and C makes them available, though the syntax is a tad odd. Since the syntax is odd, I’ll use the ALL CAPS version of their names in the explanation instead of their character.

These operations are known as bit manipulation or bit twiddling.

C provides four bit manipulation operations, NOT, AND, OR, and XOR.

NOT

Negation, when done on binary data, is known as the NOT operation and is done with the “~” operator. If we have an 8-bit unsigned variable called val with a value of 15, it has the binary value 0000 1111 (0x0F).

uint8_t val = 15;
uint8_t result;

Applying the ~ operator makes all of the 0 bits into 1s and all of the 1s in to 0s, so the value of ~val in binary is 1111 0000 or 0xF0 in hex or 240 in decimal.

result = ~val;

The value of result is now 240. If you’re not clear on why the value is 240, please stop and watch this video.

If you are working with a uint8_t value, it will operate on 8 bits simultaneously. A uint64_t will do the operation on 64 bits simultaneously if the processor supports 64 bit values.

OR

Like the logical or, the binary OR operation sets the result on if either input is on. However the binary OR operates on pairs of bits. The values are calculated with the least significant bit of one with least significant bit of the other, the next with the next, and continuing to the most significant bit with most significant bit.

The OR operation uses the “|” character, otherwise known as stick, pipe, or vertical bar.

uint16_t x = 0xAAAA;         // Give x the pattern 1010101010101010
uint16_t y = 0x00FF;         // Give y the pattern 0000000011111111
uint16_t result;

result = x | y;              // Result will be     1010101011111111

OR can be used to turn bits on in a value:

x = 0xC0;       //  This has the pattern           1100 0000
y = 1 << 4;     // shift 1 left four places giving 0001 0000

result = x | y; //                          Giving 1101 0000

This turns on the fifth bit.

AND

The binary AND operation works very much like the logical and, it uses two values and applies the and operation on each pair of bits in the values. The AND operation is indicated with the single ampersand (“&”).

uint16_t x = 0xAAAA;         // Give x the pattern 1010101010101010
uint16_t y = 0x00FF;         // Give y the pattern 0000000011111111
uint16_t result;

result = x & y;              // Result will be     0000000010101010

For each bit position, if both of the bits are 1 (on), the result has that bit on. Every other combination will lead to a bit that is off.

This is very useful for turning particular bits off in variables. If we want to turn off the 5th bit, we need to use mask;

x = 240;    //  This has the pattern                 1111 0000
y = 0x10;   // Our bit selection mask         giving 0001 0000
y = ~y;     // Invert it                      giving 1110 1111

result = x & y; //                            Giving 1110 0000

Any bit with a 1 in the mask is left unchanged, any bits with a 0 in the mask is turned off. The mask (0x10) can also be generated with the bit-shift expression 1 << 4.

XOR

XOR is also known as the exclusive-or operation. C doesn’t have an equivalent xor logical operation like & and | do, and I’m not sure that anybody has ever missed it. XOR uses the caret mark “^”.

XOR works on two values, and is true if one and only one of the values is true/on/1. Its truth table looks like:

XOR

  
    A
    B
    A ^ B
  

    TRUE
    TRUE
    FALSE
  

    FALSE
    TRUE
    TRUE
  

    TRUE
    FALSE
    TRUE
  

    FALSE
    FALSE
    FALSE
  

In code, it acts like the truth table for on each bit in the variable:

uint8_t x = 0xAA;         // Give x the pattern 10101010
uint8_t y = 0xFF;         // Give y the pattern 11111111
uint8_t result;

result = x ^ y;           // Result will be     01010101

XOR is used extensively in simple checksums, and cryptography. But the best thing that I have used XOR for is the homework this week:

Assume:

a = 42;
b = 17;
result = a;

What is the value of result at each stage of this code:

result = (result ^ a) ^ b;
result = (result ^ a) ^ b;
result = (result ^ a) ^ b;

Why?

I was asked why anybody would use bit manipulation, there are quite a few reasons in embedded systems programming:

Register bit setting - device registers in microcontrollers use their various bits to configure the device settings. You will have to set or clear groups or individual bits to set the features you need. Using the AND, OR, and NOT operators is very commonly done.
Memory allocation bitmaps - your program may have a block of memory that gets divided up into pieces. To indicate when a particular block is in use, you can set a single bit in a bitmap. A uint32_t value can be a bitmap for 32 blocks of memory. An array of N uint32_t values would keep track of N*32 blocks. You would use AND, OR, NOT and the shift operators to make and apply masks for the bitmap bits.
Bit-banging - bit banging is a method of toggling GPIO bits on and off to simulate a peripheral that your processor does not support. When dealing with very low end processors it is common to use bit banging to simulate a UART, SPI, or I2C bus. Even on PCs, it was common to use a parallel printer port to bit-bang microcontroller debugger ports. Since the GPIO pins are ganged in groups of 8 or 16 on a port, and you are only bit-banging a few of the pins, you would use AND, OR, and NOT to turn the pins on and off in the GPIO port data register.
Checksums - the XOR operator is used in simple error detecting codes. The longitudinal redundancy check is the XOR of all of the values in a data block. For 8-bit values, it looks like:

uint8_t lrc = 0;
uint8_t i;
uint8_t dataBlock[10] = { 4, 17, 63, 3, 92, 156, 240, 99, 17, 42};

for ( i = 0; i < 10; i++) {
  lrc = lrc ^ dataBlock[i];
}

This gives you a simple check byte that is transmitted with the data block. The receiver then runs the same algorithm on the received data and should get the same check byte value if the data is transmitted correctly. This code will detect any single bit error, but cannot correct any errors.

This is not nearly an exhaustive list of uses for bit manipulation operators. Can you think of any others? Please leave them in the comments with an explanation of how they work.

This post is part of a series. Please see the other posts here.