Skip to main content

Section 4.8 Expressions

In C, computations are represented as expressions. C provides a number of binary and unary arithmetic operators. Some of them are overloaded: The same symbol is used for different operand types. For example, the processor needs to perform different operations for adding two floating-point numbers than for adding two integers, but both are represented with the same symbol in C. The C compiler uses the types of the operands to determine which operation is used; the overloading is therefore resolved during the compilation.

For all types \(i \in \{\mathtt{int},\mathtt{long}\}\) and all numerical types \(f \in \{\mathtt{int},\mathtt{long},\mathtt{float},\mathtt{double}\}\text{,}\) C provides the following arithmetic operators:

Table 4.8.1. Arithmetic operators in C
Symbol Signature Description
~ \(i\to i\) bitwise negation
! \(i\to \mathtt{int}\) logical negation
+ - \(f\to f\) unary plus, minus
+ - * / \(f\times f\to f\) addition, subtraction,
multiplication, division
% \(i\times i\to i\) modulus in division
& | ^ << >> \(i\times i\to i\) bitwise and, or, xor, shifts
== != <= < >= > \(f\times f\to \mathtt{int}\) comparisons

Subsection 4.8.1 Implicit Type Conversions

If the types of an operators operands do not match, C performs a number of implicit conversions on the operands before applying the operator. Consider the following example:

int x;
double d;
...
d = d + x;

The addition operator is not defined for a double and an int (see Table 4.8.1). Following the hierarchy shown below, C converts the int operand to a double value.

Figure 4.8.2. Implicit type conversion for operands of arithmetic operators. All operands are converted to the least common type greater than or equal to int.

The implicit conversions adjust the operands to the least common operand type, where \(a\text{ "less than" }b \iff a \rightarrow^\ast b\text{.}\) Additionally, no operation is performed with operand types “less than” int. The motivation for this choice is that an int has usually the width of a machine word, for which the fastest operations of the processor are designed.

Remark 4.8.3.

When such conversions are applied, the compiler needs to emit machine code that transforms a bit sequence representing the int into a bit sequence representing a double of the same numerical value. For some types (like 64-bit long to 64-bit double), this conversion is not exact due to the double's limited precision.

Subsection 4.8.2 L- and R-Evaluation of Expressions

In C (and derived imperative languages) there are two different ways used to evaluate expressions, depending on the position of the expression. Consider the assignment

x = x + 1;

In C, assignments are expressions, meaning that = is just a binary operator. As a side effect (see Table 4.8.4), the operator stores the value resulting from the right-hand-side expression to the container whose address results from evaluating the expression of the left-hand side.

Consequently, the left operand of = needs to be evaluated as an address, whereas the right one should yield a value. In our example, a subexpression with the variable name x occurs on both sides of the operator. On the right-hand side, the subexpression x is evaluated by reading the content of the container bound to x. This evaluation to the container content is called R-evaluation. The resulting value is than incremented by 1 to compute the value of the right operand of =. On the left-hand side, x is evaluated as the address of the container bound to the variable x. We call this L-evaluation, as it occurs on the left side of the assignment.

Every expression can be R-evaluated, but some cannot be L-evaluated. To be L-evaluable, an expression needs to refer to the address of a container. For example, 1 + 2 cannot be L-evaluated, whereas x (where x is a declared variable) can. We can statically decide whether an expression is L-evaluable. The compiler aborts the translation with an error message if it finds an expression that is not L-evaluable at a position where L-evaluation is required.

If an expression \(e\) is L-evaluable, R-evaluating \(e\) results in the content of the container referred to by the L-evaluation of \(e\text{.}\)

Subsection 4.8.3 Side Effects

A particular quirk of C is that evaluating expressions can have side effects. During expression evaluation, the contents of containers may be changed, the program can interact with the operating system (for example to print text on the screen, to send network packets, to read or write files, etc.), or the evaluation might even diverge (i.e. never terminate). Table 4.8.4 shows all C operators with side effects.

Table 4.8.4. Operators with side effects. \(\oplus\) represents an arbitrary binary operator (see Table 4.8.1). The expression \(e\) needs to be L-evaluable for these operators.
Expression Name Value of the Expression Side Effects
\(\mathtt{++e}\) pre-increment new value of \(\mathtt{e}\) write \(\mathtt{e + 1}\) to \(\mathtt{e}\)
\(\mathtt{--e}\) pre-decrement new value of \(\mathtt{e}\) write \(\mathtt{e - 1}\) to \(\mathtt{e}\)
\(\mathtt{e++}\) post-increment old value of \(\mathtt{e}\) write \(\mathtt{e + 1}\) to \(\mathtt{e}\)
\(\mathtt{e--}\) post-decrement old value of \(\mathtt{e}\) write \(\mathtt{e - 1}\) to \(\mathtt{e}\)
\(\mathtt{e1 = e2}\) assignment new value of \(\mathtt{e1}\) write \(\mathtt{e2}\) to \(\mathtt{e1}\)
\(\mathtt{e1 \mathrel{\oplus=} e2}\) assignment new value of \(\mathtt{e1}\) write \(\mathtt{e1\oplus e2}\) to \(\mathtt{e1}\)
\(\mathtt{f(...)}\) function call \(\mathtt{f}\)'s return value \(\mathtt{f}\)'s side effects

The assignment is an expression with side effects:

x = x + 1

The side effect is that the value evaluated from the right-hand side is written to the container referred to by the left-hand operand. The written value is also the value of the expression.

If an expression has more than one side effect, different evaluation orders might lead to different results. Consider the following example:

          x = 5;
          y = (x = 2) * (++x);
        

The meaning of this program could be defined in several ways:

  1. A non-deterministic semantics, meaning that both, 2 and 3, would be correct results for the contents of x after the statements.

  2. With a defined order in which the subexpressions are to be evaluated (as it is done in the programming language Java).

  3. With no semantics at all (as it is done in C). The exact rules on when an expression with side effects has a semantics in C is complicated. As a rule of thumb, we can assume the evaluation of an expression to be undefined if it writes more than once into the same container. This does not extend to side effects in called functions:

                    int a(void) { printf("A"); return 1; }
                    int b(void) { printf("B"); return 2; }
                    int c(void) { return a() + b(); }
                  

    Every call to c returns the value 3. However, either of AB and BA are correct outputs of the program. Since the rules for side effects in C are complicated and easy to misunderstand, it is best to reduce side effects to a minimum: At most one operator with side effects per expression.

Subsection 4.8.4 Lazy Evaluation

C has three operators whose operands are evaluated lazily rather than strictly. An operator is subject to strict evaluation, if all its operands are evaluated before its value is computed. If it is evaluated lazily, operands are only evaluated if they contribute to the result.

Table 4.8.5. Operators that are evaluated lazily
Operator Signature Behavior
e ? t : f \(\mathtt{int} \times T \times T \to T\) if e evaluates to \(0\text{,}\) evaluate f,
\(\) \(\quad\)and t otherwise
e1 && e2 \(\mathtt{int} \times \mathtt{int} \to \mathtt{int}\) e1 == 0 ? 0 : e2
e1 || e2 \(\mathtt{int} \times \mathtt{int} \to \mathtt{int}\) e1 != 0 ? 1 : e2

Subsection 4.8.5 Exercises

The goal of this exercise is to learn how bit operations that you have encountered in the previous sections are realized in C.

C Arithmetic
a & b \(a \band b\)
a ^ b \(a \bxor b\)
a | b \(a \bor b\)
a << b \(a \bsll b\)
a >> b \(a \bsrl b\)
~a \(\overline{a}\)

Write a functions with the prototype

      unsigned int f(unsigned int k, unsigned int n);
    
  1. that flips the k-th bit in n if k is between 0 and 31.

  2. that sets the k-th bit in n if k is between 0 and 31.

  3. that clears the k-th bit in n if k is between 0 and 31.

  4. that rotates n by k to the left if k is between 1 and 31.

  5. that rotates n by k to the right if k is between 1 and 31.

You may assume here that unsigned int represents 32-bit unsigned integers.

202207281550
Solution.

unsigned int f1(unsigned int n, unsigned int k) {
  assert(k < 32);
  unsigned int a = 1 << k;
  return n ^ a;
}

unsigned int f2(unsigned int n, unsigned int k) {
  assert(k < 32);
  unsigned int a = 1 << k;
  return n | a;
}

unsigned int f3(unsigned int n, unsigned int k) {
  assert(k < 32);
  unsigned int a = (unsigned int)1 << k;
  return n & ~a;
}

unsigned int f4(unsigned int n, unsigned int k) {
  assert(0 < k && k < 32);
  unsigned int s = 32;
  return (n << k) | (n >> (s - k));
}

unsigned int f5(unsigned int n, unsigned int k)
{
  assert(0 < k && k < 32);
  unsigned int s = 32;
  return (n << (s - k)) | (n >> k);
}