2.4. Bitwise operators

Fun fact: why do computers use the binary system?

A wire may have two logical states (logical levels) represented usually by two different voltages (but in some logic families current is used). Each logic family has a threshold that delimits the “low” state from the “high” state. The “low” state represents a “0”, whereas the “high” state is a logical “1”.

The voltage for one value or the other is not fixed, because in real life there can be interferences across the wire. For example, if we have a voltage that can vary between 0 and 5V, the “low”/”0” state can be represented by the interval 0-2V and the “high”/”1” state by the interval 3-5V. Notice that there is a safety gap between the intervals to make sure they do not overlap. The device behaviour in this interval is not defined.

Because of the high variance of voltage across the wire, it is safer to only fit 2 states instead of 10. In our 0-5V example, it would be hard to distinguish a value of 8 or 9 logic (for a decimal system) for the 4.8V voltage.

Bits and Bytes

Bit

A bit represents a Binary digIT. This means that it can take one of the two values: 0 or 1. Its symbol is a lowercase “b”. This is the smallest unit used in computing.

Byte (Octet)

A byte represents an array of 8 bits. Its symbol is an uppercase “B”. One bit can represent 2 values. How many values can a byte represent?

  • Answer: values: from 0 to 255.

Bit numbering

Bit numbering represents the convention used to identify the order of bits in a byte. This refers to which bit is considered to be 0.

  • The LSB (Least Significant Bit) or the right-most bit in a byte is the bit that tells us if a number is odd or even. In the C/C++ language, the LSB is bit 0.
  • The MSB (Most Significant Bit), also called the high-order bit, is the left-most bit, the one that has the greatest value in our binary number.

Fun fact: A nibble is the unit representing 4 bits. This means that it can store different values, enough to store a single hexadecimal digit. In this respect, it is often called a “hexit” (HEX digIT).

C data types

Different data types occupy a different amount of space. The basic data types in C and their corresponding storage size are:

  • char – 1 byte
  • int – 4 bytes
  • float – 4 bytes
  • double – 8 bytes

Optional: Registers

Registers are small on-chip memory units that are very fast. They are usually named with respect to the number of bits they can hold: “8-bit register”, “32-bit register” etc.

In a microcontroller-based system, configurations are made by setting and clearing bits in configuration registers, according to the datasheet of each microcontroller. Some registries are used to read the status of ongoing operations, whereas other registers are used to store important data (e.g. the result of a conversion operation).

Converting integers from binary to decimal

Each bit in a binary number represents a power of 2 if the bit is set (equal to “1”) or 0 if the bit is cleared (equal to “0”). The LSB represents 20, the bit left to it represents 21 and so on and so forth. In order to form the decimal number from the binary one we must sum up the corresponding elements representing the power of two for each set bit. o Example:

Optional: binary to octal base

Because , it is easy to divide a binary number in groups of 3 bits (from right to left; use a padding of 0s if the last group has less than 3 bits). Then, each of these groups can be transformed into its octal value and the resulting number is the initial binary number expressed in the octal base.

Example:

Optional: binary to hexadecimal base

Because , it is easy to divide a binary number in groups of 4 bits (from right to left; use a padding of 0s if the last group has less than 4 bits). Then, each of these groups can be transformed into its hexadecimal value and the resulting number is the initial binary number expressed in the hexadecimal base.

Example:

Converting integers from decimal to binary

The simplest method for converting a decimal integer to a binary one is the division by two with remainder. This implies dividing the number by two in each iteration until it reaches 0. Each time we take the remainder of this operation and write it from left to right to form the desired binary number.

Counting in binary is fairly easy: 0+0 = 0; 1+0 = 0+1 = 1; 1+1 = 10. Below you can observe the sequence of numbers going from 0 to 20 (decimal, left side) together with their binary correspondents (right side).

 0 =     0
 1 =     1
 2 =    10
 3 =    11
 4 =   100
 5 =   101
 6 =   110
 7 =   111
 8 =  1000
 9 =  1001
10 =  1010
11 =  1011
12 =  1100
13 =  1101
14 =  1110
15 =  1111
16 = 10000
17 = 10001
18 = 10010
19 = 10011
20 = 10100

Optional: octal base to binary

Because , by expanding each octal digit into its 3-digit binary form we get the corresponding binary form of the original number.

Example:

Optional: hexadecimal base to binary

Because , by expanding each octal digit into its 4-digit binary form we get the corresponding binary form of the original number.

Example:

Optional: Why do we also use the octal and hexadecimal systems?

We mainly use these systems for our convenience, because it is makes the code much clearer. We can easily use only 2 hexadecimal digits to represent a byte and the C compiler will internally translate it into a binary value.

The octal base system is rarely used, but there are examples where it is preferable. For instance, in the Unix systems there are three types of privileges associated with a file: read, write and execute. Each privilege can be expressed differently for the owner of the respective file, the current user and groups (OUG). In this respect, there is a flag bit associated for each privilege in each of these cases, resulting in 9 bits grouped three-by-three for each file. Thus, it is convenient to use only one digit for coding the privilege levels for each case (owner, user, group).

What is a bitwise operation?

A bitwise operation operates on one or more bits of a bit field or binary numeral. Because these actions are directly supported by the processor, they are significantly faster than division, multiplication and even addition.

In this section we are referring to the bitwise operations used in the standard C programming language. Bit indexing begins at 0, not 1. Bit 0 is the least significant bit.

Truth tables correspondence

The ‘0’ bit corresponds to the “false” value, whereas ‘1’ means a value is “true”. By replacing the “true” and “false” values in the tables from the previous section with 1s and 0s the results will reflect the application of that respective bitwise operator.

Examples:

  • 0 & 1 = 0
  • 0110 | 1010 = 1110
  • int i = 0, j; for(j=0; j<10; j++) { i = i ^ 1; printf(“%i\n”, i); }
    • variable “i” toggles between 1 and 0

Shift operations

There are two bitwise shift operations in C: right shift (“»”) and left shift (“«”).

Right shift

Right shift shifts each bit in the left operand to the right. The right operand represents the number of places with which the bits in the left operand are shifted. If need be, zeroes are automatically appended to the left of the number to preserve its size.

Examples:

Right shift can be used to divide a binary number by two in a single operation. Example: 1010 » 1 = 0101.

  • 1010(base 2) = 10(base 10)
  • 0101(base 2) = 5(base 10)
Left shift

Shifts each bit in the right operand to the left. The right operand represents the number of places with which the bits in the left operand are shifted. Zeroes are automatically appended to the right of the number to preserve its size.

Examples:

Left shift can be used to multiply a binary number with two in a single operation. Example: 1010 « 1 = 10100.

  • 1010(base 2) = 10(base 10)
  • 10100(base 2) = 20(base 10)

Bit manipulation

Bitwise complement

~Byte

Union

Byte1 | Byte2

Intersection

Byte1 & Byte2

Substraction

Byte1 & ~Byte2

Bit Mask

A bit mask is used to set or clear multiple bits in a bit field (nibble, byte etc.) in a single operation.

  • Mask bits to 1
    • This operation is easily done through the bitwise OR with 1s. If a bit was 1 before this operation, it will be left unchanged (1 | 1 = 1), but if the bit was 0 prior to the operation, then its value will be changed to 1 (0 | 1 = 1).
    • Example:
  • Mask bits to 0
    • In order to change bits to 0 we use the bitwise AND with 0s. If a bit was 0 prior to the operation, it will remain unchanged (0 & 0 = 0), but if its value was 1 it will change to 0 (1 & 0 = 0).
    • Example:
  • Querying the status of a bit
    • By performing the AND operation with a 1 in the place of the bit we wish to query we get the status of that respective bit. After this, we can apply a comparison with 0 or 1 to check which state it is in.
    • Examples:
      • if(11011 & 00010) {…} else {…}
  • Toggling bit values
    • In order to set bits on and off in the same operation, we need to use the bitwise XOR operation. According to the truth table: 1 XOR 1 = 0, 0 XOR 1 = 1 and 0 XOR 0 = 0.
    • Note: XOR does not affect unmasked bits. If you want certain bits to remain the same, you need to set their respective bits in the mask to 0.
    • Example:

Set a bit in a byte

Byte|= (1 « Bit_index)

Clear a bit from a byte

Byte &= ~(1 « Bit_index)

Toggle

Byte ^= (1 « Bit_index)

Test

Byte & (1 « Bit_index)

Common mistakes

  • Indexing begins from 0 in C!
  • Confusing the “!” and “~” operators. “!” transforms any “false” (=0) statement in a “true” one and vice-versa, whereas “~” transforms all the 0s in a bit filed into 1s and vice-versa.
    • Example: !1100 = 0; ~1100 = 0011
  • Confusing the “&” and “&&” operators. “&” performs the logical AND between the corresponding bits of the respective numbers. “&&” returns the truth state of the expression evaluated according to the AND truth table (1 AND 1 represents true = 1, everything else results in false = 0).
  • Confusing the “|” and “||” operators. “|” performs the logical OR between the corresponding bits of the respective numbers. “||” returns the truth state of the expression evaluated according to the OR truth table (0 OR 0 represents false = 0, everything else results in true = 1).
  • Let's say you have a byte Byte and a bit index Bit_index of a bit that belongs to Byte. If you want to set the bit at index Bit_index, it is wrong to just do the following: Byte = 1«Bit_index. This will clear all the other bits except the one being set. The correct way to do it is: Byte |= 1«Bit_index. For example, if Byte = 11001110 and Bit_index = 4:
    • WRONG way: Byte = 1«4; ⇒ Byte will become: 00010000
    • CORRECT way: Byte |= 1«4; ⇒ Byte will become: 11011110
  • Let's say you have a byte Byte and a bit index Bit_index of a bit that belongs to Byte. If you want to clear the bit at index Bit_index, it is wrong to just do the following: Byte = ~(1«Bit_index). This will clear all bits in Byte. The correct way to do it is: Byte &= ~(1«Bit_index). For example, if Byte = 11001110 and Bit_index = 2:
    • WRONG way: Byte = ~(1«2); ⇒ Byte will become: 00000000
    • CORRECT way: Byte &= ~(1«2); ⇒ Byte will become: 11001010
roboticsisfun/chapter2/ch2_4_bitwise_operators.txt · Last modified: 2013/02/12 00:41 by silvia.stegaru