Introduction to C++¶

Part 2 · Programming languages · Chapter 6 · Lecture notes, volume 2 (PDF) · Exercises: Introduction to C++

Introduction¶

In the chapter «Pseudo-code» algorithms are written in a language meant for humans: it is precise, but it is not executed by a computer. To run an algorithm we have to translate it into a programming language. In this chapter we introduce the programming language C++, which we use to implement the algorithms of the course.

The chapter follows the same path as the chapter «Pseudo-code»:

the main characteristics of the language and the structure of a program;
variables, data types and the input-output stream;
operators, conditional statements and loops;
arrays, whose size can be fixed or decided during the execution;
functions, with the main function as the entry point of every program;
a complete algorithm, the search of the maximum value in an array, written in pseudo-code and in C++;
the bitwise operators, which act directly on the binary representation of integer numbers.

Every fragment of code of the chapter has been compiled with the g++ compiler (standard C++17) and executed: the outputs reported in the examples are the ones printed by the programs.

In pseudo-code the entries of an array \(a[1..n]\) are indexed from \(1\) to \(n\); in C++ the entries of an array of size \(n\) are indexed from \(0\) to \(n-1\). The entry \(a[i]\) of the pseudo-code corresponds to the entry a[i-1] of the C++ code.

6.1 Main characteristics of the programming language¶

The main characteristics of C++ are the following.

C++ is an imperative language that gives direct access to the memory and to the hardware resources of the computer. It is highly efficient for low-level system programming while also supporting high-level abstractions, making it versatile for both performance-critical applications and modern software development.
C++ supports functions, which enable a structured and modular approach to programming. Functions allow code reuse and better organization.
The C++ programming language includes a predefined set of reserved symbols used to declare variables, define functions and specify executable instructions. The source code consists of a sequence of atomic operations executed in order, one after the other, operating on variables of specific data types.
The source code in C++ can contain comments, which serve as documentation for the code and are ignored by the compiler. In C++, a single-line comment starts with the reserved symbol “//”. Multi-line comments are enclosed between the reserved symbols “/*” and “*/”.

Example 6.1: comments in C++

This is an example of a single-line comment:

// This is a comment line

This is an example of a multi-line comment:

/* This is a
   multi-line comment */

6.1.1 The structure of a program¶

Before describing the single instructions, we look at the skeleton that every program shares. A C++ program is a text file (with extension .cpp) that is translated by a compiler into an executable file. The execution of the program starts from the main function, the entry point of every program.

Example 6.2: the skeleton of a program

#include <iostream>

using namespace std;

int main()
{
    // The instructions of the program are written here
    cout << "Hello, world!" << endl;

    return 0;
}

If the source code is saved in the file hello.cpp, it is compiled and executed with the commands

g++ -Wall -std=c++17 -o hello hello.cpp
./hello

and the output is

Hello, world!

In the following examples we write only the instructions that matter: unless they contain a complete program, the fragments of code are meant to be placed inside the curly braces of main.

Each instruction of a C++ source code must end with the reserved symbol “;”.

6.2 Variables and data types¶

The source code operates on variables, and every variable has a data type.

Information is categorized into different data types. The four fundamental families of data types are:
1. The data type “int” represents an integer, which is a whole number written without a decimal point. This includes positive and negative whole numbers, as well as zero.
2. The data type “bool” represents a Boolean value: true or false.
3. The data type “float” represents a floating-point number, which includes numbers written with a decimal point. The data type “double” represents a floating-point number with double precision, providing greater accuracy and range than float.
4. The data type “char” represents a single character, such as a letter, digit, or symbol, enclosed in single quotes (e.g., 'A', '7', '!').
A sequence of characters enclosed in double quotes (e.g., "Ada") is stored in a variable of type “string”, provided by the standard library <string>.
A variable acts as a container that stores a value of a specific data type for later use. Each variable has a unique name and holds a single value at any given time.
Variables are assigned values using the assignment operator “=”. When a new value is assigned, the previous value is overwritten.

Variables must be declared before use, specifying their data type.

Example 6.3: variable declarations and value assignments

int age = 25; // Integer variable
bool isRaining = false; // Boolean variable
float smallNumber = 3.14; // Floating-point variable
double largeNumber = 123456.789; // Double precision floating-point variable
char character = 'a'; // Char variable
string name = "Ada"; // String variable

age = 26; // The previous value 25 is overwritten
cout << age << " " << isRaining << " " << smallNumber << " "
     << largeNumber << " " << character << " " << name << endl;

Output:

26 0 3.14 123457 a Ada

The Boolean value false is displayed as 0, and the number 123456.789 is displayed as 123457: by default, cout displays at most six significant digits (the value stored in the variable does not change, and the number of displayed digits can be chosen, as we see now).

6.3 Input-output stream¶

To display the values of the variables on the screen, a program uses the input-output stream library.

The include “#include <iostream>” allows to use the input-output stream library in C++.

Example 6.4: include

#include <iostream>

The values of variables can be displayed as output text on the screen using the output stream “std::cout”. The insertion operator “< <” is used to send data to the output stream.
Multiple values can be displayed in a single cout statement by chaining them with the “< <” operator. Text should be enclosed in double quotes “"”, while variable values are written directly.
The manipulator “std::endl” is used with std::cout to insert a new line on the screen and flush the output buffer.

Example 6.5: screen printings

int n = 7;
std::cout << "The value of the variable is " << n << std::endl;

Output:

The value of the variable is 7

The statement “using namespace std;” simplifies the use of standard library functions by eliminating the need to prefix them with std::. From now on we always use it, and we write cout and endl.
The include “#include <iomanip>” gives the manipulators “fixed” and “setprecision(k)”. When they are written together in a cout statement, they display the floating-point numbers that follow with exactly \(k\) digits after the decimal point.

6.4 Operators¶

Operators are symbols that perform operations on variables and values. They are classified, according to their functionality, into five main categories: arithmetic, assignment, increment and decrement, relational and logical operators.

6.4.1 Arithmetic operators¶

Arithmetic operators, used to perform basic mathematical operations:

+ (Addition) \(\rightsquigarrow\) Adds two values.
- (Subtraction) \(\rightsquigarrow\) Subtracts one value from another.
* (Multiplication) \(\rightsquigarrow\) Multiplies two values.
/ (Division) \(\rightsquigarrow\) Divides one value by another.
% (Modulus) \(\rightsquigarrow\) Returns the remainder of a division.

Example 6.6: arithmetic operators

int a = 10, b = 3;

cout << "Addition: " << (a + b) << endl;
cout << "Subtraction: " << (a - b) << endl;
cout << "Multiplication: " << (a * b) << endl;
cout << "Division: " << (a / b) << endl; // Integer division
cout << "Modulus: " << (a % b) << endl; // Remainder of division

Output:

Addition: 13
Subtraction: 7
Multiplication: 30
Division: 3
Modulus: 1

The division operator / performs integer division when used with integers: the result 10 / 3 is 3. To obtain a floating-point result, at least one operand must be of data type float or double. For example, 10.0 / 3 returns 3.33333 instead of 3.
A value of type int is converted into a value of type double by writing “(double)” before it (type conversion). For example, if a and b are variables of type int, the expression (double)a / b performs the floating-point division.

Example 6.7: integer and floating-point division

int a = 10, b = 3;

cout << a / b << endl;          // Integer division: 3
cout << 10.0 / 3 << endl;       // Floating-point division
cout << (double)a / b << endl;  // Conversion of a to double
cout << fixed << setprecision(2) << (double)a / b << endl; // Two decimals

Output (the last line requires #include <iomanip>):

6.4.2 Assignment operators¶

Assignment operators, used to assign values to variables:

= (Assignment) \(\rightsquigarrow\) Assigns a value to a variable.
+= (Addition assignment) \(\rightsquigarrow\) Adds a value to a variable and assigns the result.
-= (Subtraction assignment) \(\rightsquigarrow\) Subtracts a value from a variable and assigns the result.
*= (Multiplication assignment) \(\rightsquigarrow\) Multiplies a variable by a value and assigns the result.
/= (Division assignment) \(\rightsquigarrow\) Divides a variable by a value and assigns the result.
%= (Modulus assignment) \(\rightsquigarrow\) Applies the modulus operation and assigns the result.

Example 6.8: assignment operators

int x = 10;  // Assignment
cout << "Initial value: " << x << endl;

x += 5;  // Equivalent to: x = x + 5
cout << "After += 5: " << x << endl;

x -= 3;  // Equivalent to: x = x - 3
cout << "After -= 3: " << x << endl;

x *= 2;  // Equivalent to: x = x * 2
cout << "After *= 2: " << x << endl;

x /= 4;  // Equivalent to: x = x / 4
cout << "After /= 4: " << x << endl;

x %= 3;  // Equivalent to: x = x % 3
cout << "After %= 3: " << x << endl;

Output:

Initial value: 10
After += 5: 15
After -= 3: 12
After *= 2: 24
After /= 4: 6
After %= 3: 0

6.4.3 Increment and decrement operators¶

Increment and decrement operators:

++ (Increment) \(\rightsquigarrow\) Increases the value of a variable by 1.
- - (Decrement) \(\rightsquigarrow\) Decreases the value of a variable by 1.

The increment operator ++ can be used in two forms:
- pre-increment (“++x”): increments the value before returning it;
- post-increment (“x++”): returns the value first, then increments it.
The same logic applies to the decrement operator (- -x and x- -).

Example 6.9: increment and decrement operators

int x = 5;

cout << "Initial value: " << x << endl; // Displays 5

cout << "Pre-increment (++x): " << ++x << endl; // Displays 6

cout << "Post-increment (x++): " << x++ << endl; // Displays 6
cout << "Value after post-increment: " << x << endl; // Displays 7

cout << "Pre-decrement (--x): " << --x << endl; // Displays 6

cout << "Post-decrement (x--): " << x-- << endl; // Displays 6
cout << "Value after post-decrement: " << x << endl; // Displays 5

Output:

Initial value: 5
Pre-increment (++x): 6
Post-increment (x++): 6
Value after post-increment: 7
Pre-decrement (--x): 6
Post-decrement (x--): 6
Value after post-decrement: 5

6.4.4 Relational operators¶

Relational operators, used to compare values and return a Boolean result:

== (Equal to) \(\rightsquigarrow\) Checks if two values are equal.
!= (Not equal to) \(\rightsquigarrow\) Checks if two values are different.
< (Less than) \(\rightsquigarrow\) Checks if one value is smaller than another.
> (Greater than) \(\rightsquigarrow\) Checks if one value is larger than another.
<= (Less than or equal to) \(\rightsquigarrow\) Checks if one value is smaller than or equal to another.
>= (Greater than or equal to) \(\rightsquigarrow\) Checks if one value is larger than or equal to another.

Relational operators return a Boolean result:
- true (displayed as 1) if the condition is satisfied;
- false (displayed as 0) if the condition is not satisfied.
These operators are commonly used in conditional statements and loops.

Example 6.10: relational operators

int a = 10, b = 5;

cout << "a == b: " << (a == b) << endl;  // Equal to
cout << "a != b: " << (a != b) << endl;  // Not equal to
cout << "a < b: " << (a < b) << endl;    // Less than
cout << "a > b: " << (a > b) << endl;    // Greater than
cout << "a <= b: " << (a <= b) << endl;  // Less than or equal to
cout << "a >= b: " << (a >= b) << endl;  // Greater than or equal to

Output:

a == b: 0
a != b: 1
a < b: 0
a > b: 1
a <= b: 0
a >= b: 1

6.4.5 Logical operators¶

Logical operators, used for logical operations, often in conditional statements:

&& (Logical AND) \(\rightsquigarrow\) Returns true if both conditions are true.
|| (Logical OR) \(\rightsquigarrow\) Returns true if at least one condition is true.
! (Logical NOT) \(\rightsquigarrow\) Reverses the Boolean value.

Like the relational operators, logical operators return Boolean values, true (1) or false (0), and are commonly used in conditional statements and loops.

Example 6.11: logical operators

bool condition1 = true;
bool condition2 = false;

cout << "condition1: " << condition1 << endl;
cout << "condition2: " << condition2 << endl;

// Logical AND: true only if both conditions are true
cout << "condition1 && condition2: " << (condition1 && condition2) << endl;

// Logical OR: true if at least one condition is true
cout << "condition1 || condition2: " << (condition1 || condition2) << endl;

// Logical NOT: reverses the Boolean value
cout << "!condition1: " << !condition1 << endl;
cout << "!condition2: " << !condition2 << endl;

Output:

condition1: 1
condition2: 0
condition1 && condition2: 0
condition1 || condition2: 1
!condition1: 0
!condition2: 1

6.5 Conditional statements¶

The relational and logical operators produce the conditions that decide which instructions are executed.

Conditional statements allow to execute different blocks of code based on specific conditions. The if statement is the most fundamental control structure of this type.
The if statement evaluates a condition inside parentheses (). If the condition is true, the block of code inside the curly braces {} is executed. If the condition is false, the program skips the block and executes the block of code inside the curly braces {} of the else part, if present.

Example 6.12: conditional statement

int number = 10;

// Check if number is positive
if (number > 0)
{
    cout << "The number is positive." << endl;
}
else
{
    cout << "The number is non-positive." << endl;
}

Output:

The number is positive.

6.5.1 Ternary operator (conditional operator)¶

The ternary operator ?: provides a compact way to write simple if-else statements.
It is the only operator in C++ that takes three operands.
Syntax: condition ? value_if_true : value_if_false
If the condition is true, the expression evaluates to value_if_true; otherwise, it evaluates to value_if_false.

Example 6.13: ternary operator

int number = 10;

// Using if-else statement
string result1;
if (number > 0)
    result1 = "positive";
else
    result1 = "non-positive";

cout << "The number is " << result1 << endl;

// Using ternary operator (compact form)
string result2 = (number > 0) ? "positive" : "non-positive";

cout << "The number is " << result2 << endl;

Output:

The number is positive
The number is positive

Example 6.14: finding the maximum of two numbers

int a = 15, b = 20;

// Using if-else statement
int max1;
if (a > b)
    max1 = a;
else
    max1 = b;

cout << "Maximum (if-else): " << max1 << endl;

// Using ternary operator (compact form)
int max2 = (a > b) ? a : b;

cout << "Maximum (ternary): " << max2 << endl;

Output:

Maximum (if-else): 20
Maximum (ternary): 20

Example 6.15: checking even or odd

int n = 7;

// Using ternary operator
string parity = (n % 2 == 0) ? "even" : "odd";

cout << n << " is " << parity << endl;

Output:

7 is odd

Example 6.16: assigning the absolute value

int x = -5;

// Using ternary operator to compute absolute value
int absValue = (x >= 0) ? x : -x;

cout << "Absolute value of " << x << " is " << absValue << endl;

Output:

Absolute value of -5 is 5

Example 6.17: nested ternary operators

int score = 85;

// Nested ternary operators to assign a grade
string grade = (score >= 90) ? "A" :
               (score >= 80) ? "B" :
               (score >= 70) ? "C" :
               (score >= 60) ? "D" : "F";

cout << "Score: " << score << ", Grade: " << grade << endl;

Output:

Score: 85, Grade: B

The conditions are evaluated from top to bottom: score >= 90 is false and score >= 80 is true, so the grade is "B". For readability, complex conditions are better handled with if-else statements.

6.6 Loops¶

Conditional statements choose whether a block of code is executed; loops decide how many times it is executed.

Loops are used to execute a block of code repeatedly while a condition is met. They are essential for automating repetitive tasks and reducing redundant code. In C++, the most commonly used loops are the while loop and the for loop.

6.6.1 The `while` loop¶

The while loop executes a block of code as long as the condition inside the parentheses () evaluates to true. When the condition is false, the loop terminates.

Example 6.18: while loop

int i = 1; // Initialization

while (i <= 5) // Condition
{
    cout << "Number: " << i << endl;
    i++; // Increment
}

Output:

Number: 1
Number: 2
Number: 3
Number: 4
Number: 5

The condition i <= 5 is evaluated six times: five times it is true, and the sixth time (i equal to 6) it is false and the loop terminates.

6.6.2 The `for` loop¶

The for loop is a compact loop structure that combines initialization, condition, and increment (or decrement) in one statement.

Example 6.19: for loop

for (int i = 1; i <= 5; i++) // Initialization, condition, increment
{
    cout << "Number: " << i << endl;
}

The output is the same as in the while loop of Example 6.18.

6.6.3 The `break` and `continue` statements¶

The break statement immediately terminates the loop.
The continue statement skips the rest of the current iteration and moves to the next one.

Example 6.20: break and continue

for (int i = 1; i <= 10; i++)
{
    if (i % 2 == 0)
    {
        continue; // Skip the even numbers
    }
    if (i > 7)
    {
        break; // Stop the loop at the first odd number greater than 7
    }
    cout << i << " ";
}
cout << endl;

Output:

1 3 5 7

The even values of i are skipped by continue; when i is equal to 9 the break statement terminates the loop, and the value 10 is never reached.

6.7 Arrays¶

Loops become really useful when they visit collections of values. A collection of variables of the same data type is stored in an array.

6.7.1 Fixed-size arrays¶

An array whose values are known when the program is written can be declared by listing its values inside curly braces. The size of the array is the number of listed values, and it cannot change during the execution.
Each element of an array is accessed using its index, starting from zero, inside square brackets “[]”: the elements of an array of size \(n\) are b[0], b[1], …, b[n-1].

Example 6.21: fixed-size arrays

int b[] = {9, 12, 3, 16}; // Array of 4 integers
int n = 4;

b[2] = 5; // Assign a new value to the third element

for (int i = 0; i < n; i++)
{
    cout << b[i] << " ";
}
cout << endl;

Output:

9 12 5 16

A two-dimensional fixed-size array is declared with two sizes, the number of rows and the number of columns, and its values are listed row by row: int c[2][3] = {{3, 1, 4}, {1, 5, 9}}; declares an array with \(2\) rows and \(3\) columns, and c[1][2] is the element in the second row and third column, equal to \(9\).

6.7.2 Dynamic-size arrays¶

A dynamic-size array is a collection of variables of the same data type, stored in contiguous memory locations. The size of the array is determined during the execution of the algorithm.
The reserved symbol “*” is used to declare a pointer, which stores the memory address of the first element of a dynamic-size array. The new operator is used to allocate the memory of a dynamic-size array, and it must specify the data type of the elements along with the size of the array inside square brackets “[]”.
Each element of a dynamic-size array is accessed using its index, starting from zero, inside square brackets “[]”. A dynamic-size array requires memory deallocation using the delete[] operator to free memory and prevent memory leaks.

Figure 6.1: A dynamic-size array of size \(n\): the pointer a stores the address of the first element, and the elements are indexed from \(0\) to \(n-1\).

Example 6.22: dynamic-size arrays

int n = 5; // Size of the array

int* a = new int[n]; // Memory allocation of an array of size n

for (int i = 0; i < n; i++)
{
    a[i] = i * 2; // Example of value assignment
}

for (int i = 0; i < n; i++)
{
    cout << a[i] << " ";
}
cout << endl;

delete[] a;  // Free allocated memory

Output:

0 2 4 6 8

Dynamic-size arrays can be multidimensional. For example, the reserved symbol “**” is used to declare a pointer to a pointer, which stores the memory address of the first element of a dynamic-size two-dimensional array: an array of \(m\) pointers, each pointing to a row of \(n\) elements.
The new operator is also used to allocate the memory of dynamic-size two-dimensional arrays: first the array of the \(m\) row pointers, then each row. Each element of a dynamic-size two-dimensional array is accessed using two indices, both starting from zero, inside square brackets “[][]”. The memory is freed in the reverse order: first each row, then the array of row pointers.

Example 6.23: dynamic-size two-dimensional arrays

int m = 3; // Number of rows
int n = 4; // Number of columns

int** matrix = new int*[m]; // Memory allocation of a matrix of size m times n
for (int i = 0; i < m; i++)
{
    matrix[i] = new int[n]; // Allocate each row
}

for (int i = 0; i < m; i++)
{
    for (int j = 0; j < n; j++)
    {
        matrix[i][j] = i * j; // Example of value assignment
        cout << matrix[i][j] << " ";
    }
    cout << endl;
}

for (int i = 0; i < m; i++) // Free allocated memory
{
    delete[] matrix[i]; // Free each row
}
delete[] matrix; // Free row pointers

Output:

0 0 0 0
0 1 2 3
0 2 4 6

6.8 The `main` and custom functions¶

As in pseudo-code, an algorithm is written as a function that receives the input and returns the output.

Functions allow programmers to write modular and reusable code by grouping instructions into a single unit. A function can be called multiple times to execute the same task, reducing redundancy and improving code organization.
Functions typically return a value and accept multiple parameters as input. When calling a function, the arguments are passed to the parameters.
A function in C++ consists of:
1. a return type: specifies the type of the value returned by the function (void if nothing is returned);
2. a function name: the unique identifier of the function;
3. a parameter list (optional): specifies the input values of the function;
4. a body: contains the block of code executed when the function is called;
5. a return statement (optional): used to return a value if the function returns a value.
The main function serves as the entry point of a C++ program. It is executed first when the program starts running. Every C++ program must contain exactly one main function. Its return value 0 tells the operating system that the program terminated correctly.
A function must be defined (or declared) before the point where it is called: for this reason the custom functions are written before main.
C++ source code can also be compiled and executed online, for example at the following address: www.mycompiler.io/it/online-c++-compiler

Example 6.24: functions

#include <iostream>

using namespace std;

// Function definition
int addition(int a, int b)
{
    return a + b; // Returns the sum
}

// Function definition
int multiplication(int a, int b)
{
    return a * b; // Returns the product
}

int main()
{
    int sum = addition(5, 10); // Function call
    cout << "Sum: " << sum << endl;
    int prod = multiplication(5, 10); // Function call
    cout << "Prod: " << prod << endl;

    return 0;
}

Output:

Sum: 15
Prod: 50

6.8.1 Parameters passed by value and by reference¶

A function returns at most one value. When a function has to produce more than one result, or has to modify a variable of the caller, its parameters are passed by reference.

By default, a parameter is passed by value: the function receives a copy of the argument, and the changes made to the copy do not affect the variable of the caller.
A parameter is passed by reference by writing the reserved symbol “&” after its data type (for example int& x): the parameter is another name for the variable of the caller, and every change made by the function is visible to the caller.
An array is passed to a function through the pointer to its first element (for example int *a), together with its size: the function works directly on the elements of the array of the caller.

Example 6.25: parameters passed by value and by reference

#include <iostream>

using namespace std;

void incrementByValue(int x)
{
    x = x + 1; // Modifies only the local copy
}

void incrementByReference(int& x)
{
    x = x + 1; // Modifies the variable of the caller
}

void fillWithZeros(int n, int* a)
{
    for (int i = 0; i < n; i++)
    {
        a[i] = 0; // Modifies the array of the caller
    }
}

int main()
{
    int k = 5;
    incrementByValue(k);
    cout << "After incrementByValue: " << k << endl;
    incrementByReference(k);
    cout << "After incrementByReference: " << k << endl;

    int b[] = {4, 7, 1};
    fillWithZeros(3, b);
    cout << "Array: " << b[0] << " " << b[1] << " " << b[2] << endl;

    return 0;
}

Output:

After incrementByValue: 5
After incrementByReference: 6
Array: 0 0 0

6.9 A complete algorithm: the maximum value in an array¶

We now put all the pieces together: a function, a loop, a conditional statement and a dynamic-size array.

We consider the problem of finding the maximum value in an array \(a\) of \(n \ge 1\) integer numbers.

This is the pseudo-code of the algorithm FindMaximum of the chapter «Pseudo-code»: the entries are indexed from \(1\) to \(n\).

Algorithm: FindMaximum

Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers

Output: The maximum value in the array \(a\)

1function FindMaximum(a, n)

2\(max := a[1]\)

3for \(i := 2\) to \(n\) do

4if \(a[i] > max\) then

5\(max \leftarrow a[i]\)

6end

7end

8return \(max\)

9end

This is the C++ implementation: the entries are indexed from \(0\) to \(n-1\), so the initialization uses a[0] and the loop starts from i = 1. The function assumes \(n \ge 1\), as the pseudo-code does: for \(n = 0\) the element a[0] does not exist.

#include <iostream>

using namespace std;

// Function to find the maximum value in an array
int ArrayMaxValue(int n, int *a)
{
    int max = a[0]; // Initialize with the first element

    for (int i = 1; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i]; // Update the maximum
        }
    }

    return max;
}

int main()
{
    int n = 7; // Size of the array

    int* a = new int[n]; // Memory allocation of an array of size n

    int values[] = {9, 12, 3, 16, 19, 11, 12};
    for (int i = 0; i < n; i++)
    {
        a[i] = values[i];
    }

    int max = ArrayMaxValue(n, a);
    cout << "Maximum value: " << max << endl;

    delete[] a; // Free allocated memory

    return 0;
}

Output:

Maximum value: 19

Example 6.26: step-by-step execution

In each table, the column \(i\) is the index of the C++ loop and the column \(i+1\) is the corresponding index of the pseudo-code. The first row is the initialization max = a[0].

Instance 1: \(a = [9, 12, 3, 16, 19, 11, 12]\), \(n=7\)

\(i\) (`C++`)	\(i+1\) (pseudo-code)	`a[i]`	`a[i] > max`?	`max`
–	–	–	–	\(9\)
\(1\)	\(2\)	\(12\)	Yes	\(12\)
\(2\)	\(3\)	\(3\)	No	\(12\)
\(3\)	\(4\)	\(16\)	Yes	\(16\)
\(4\)	\(5\)	\(19\)	Yes	\(19\)
\(5\)	\(6\)	\(11\)	No	\(19\)
\(6\)	\(7\)	\(12\)	No	\(19\)

Return: max \(= 19\)

Instance 2: \(a = [3, 7, 2, 9, 1]\), \(n=5\)

\(i\) (`C++`)	\(i+1\) (pseudo-code)	`a[i]`	`a[i] > max`?	`max`
–	–	–	–	\(3\)
\(1\)	\(2\)	\(7\)	Yes	\(7\)
\(2\)	\(3\)	\(2\)	No	\(7\)
\(3\)	\(4\)	\(9\)	Yes	\(9\)
\(4\)	\(5\)	\(1\)	No	\(9\)

Return: max \(= 9\)

6.10 Bitwise operators¶

The integer numbers handled by a program are stored in binary, as described in the chapter «Representation of numbers». C++ provides operators that act directly on these binary digits.

Bitwise operators perform operations on the individual bits of integer values. They are essential for low-level programming, optimization, and working with binary representations.
The bits are numbered from the right, starting from position \(0\) (the least significant bit).

Bitwise operators in C++:

& (Bitwise AND) \(\rightsquigarrow\) Returns 1 only if both corresponding bits are 1.
| (Bitwise OR) \(\rightsquigarrow\) Returns 1 if at least one corresponding bit is 1.
(Bitwise XOR) \(\rightsquigarrow\) Returns 1 if the corresponding bits are different.
~ (Bitwise NOT) \(\rightsquigarrow\) Flips all bits (0 becomes 1, 1 becomes 0).
< < (Left shift) \(\rightsquigarrow\) Shifts the bits to the left by a specified number of positions.
> > (Right shift) \(\rightsquigarrow\) Shifts the bits to the right by a specified number of positions.

6.10.1 Bitwise AND (`&`)¶

The bitwise AND operator compares each bit of two numbers and returns 1 only if both bits are 1.
Truth table for AND:

Bit A	Bit B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

Example 6.27: bitwise AND

int a = 12;  // Binary: 1100
int b = 10;  // Binary: 1010
int result = a & b;  // Binary: 1000 (decimal: 8)

cout << "a & b = " << result << endl;  // Output: 8

Bit-by-bit operation:

				Decimal
`a`	1	1	0	12
`b`	1	0	1	10
`a & b`	1	0	0	8

6.10.2 Bitwise OR (`|`)¶

The bitwise OR operator compares each bit of two numbers and returns 1 if at least one bit is 1.
Truth table for OR:

Bit A	Bit B	A \| B
0	0	0
0	1	1
1	0	1
1	1	1

Example 6.28: bitwise OR

int a = 12;  // Binary: 1100
int b = 10;  // Binary: 1010
int result = a | b;  // Binary: 1110 (decimal: 14)

cout << "a | b = " << result << endl;  // Output: 14

Bit-by-bit operation:

				Decimal
`a`	1	1	0	12
`b`	1	0	1	10
`a \| b`	1	1	1	14

6.10.3 Bitwise XOR ()¶

The bitwise XOR (exclusive OR) operator compares each bit of two numbers and returns 1 if the bits are different.
Truth table for XOR:

Bit A	Bit B	A B
0	0	0
0	1	1
1	0	1
1	1	0

Example 6.29: bitwise XOR

int a = 12;  // Binary: 1100
int b = 10;  // Binary: 1010
int result = a ^ b;  // Binary: 0110 (decimal: 6)

cout << "a ^ b = " << result << endl;  // Output: 6

Bit-by-bit operation:

				Decimal
`a`	1	1	0	12
`b`	1	0	1	10
`a b`	0	1	1	6

6.10.4 Bitwise NOT (`~`)¶

The bitwise NOT operator flips all bits of a number (0 becomes 1, 1 becomes 0).
This is a unary operator (it operates on a single operand).
The result depends on the number of bits used to represent the integer. In the example we use the data type unsigned char, which stores the natural numbers from \(0\) to \(255\) with \(8\) bits; the conversion (int) displays the result as a number instead of a character.

Example 6.30: bitwise NOT

unsigned char a = 12;  // Binary (8 bits): 00001100
unsigned char result = ~a;  // Binary: 11110011 (decimal: 243)

cout << "~a = " << (int)result << endl;  // Output: 243

Bit-by-bit operation (using the 8-bit representation):

									Decimal
`a`	0	0	0	0	1	1	0	0	12
`~a`	1	1	1	1	0	0	1	1	243

Indeed, \(243 = 255 - 12\): flipping all the \(8\) bits of a number \(x\) gives \(255 - x\).

6.10.5 Left shift (`< <`)¶

The left shift operator shifts all bits to the left by a specified number of positions.
Zeros are added on the right side.
Shifting left by \(k\) positions is equivalent to multiplying by \(2^k\) (as long as the result can be represented by the data type).

Example 6.31: left shift

int a = 5;  // Binary: 0101
int result = a << 2;  // Shift left by 2 positions: 10100 (decimal: 20)

cout << "a << 2 = " << result << endl;  // Output: 20
// Equivalent to: 5 * 2^2 = 5 * 4 = 20

Bit-by-bit operation:

							Decimal	Equivalent
`a`	0	0	0	1	0	1	5	\(5\)
`a < < 1`	0	0	1	0	1	0	10	\(5 \times 2^1\)
`a < < 2`	0	1	0	1	0	0	20	\(5 \times 2^2\)
`a < < 3`	1	0	1	0	0	0	40	\(5 \times 2^3\)

6.10.6 Right shift (`> >`)¶

The right shift operator shifts all bits to the right by a specified number of positions; the bits that exit on the right are lost.
For non-negative integers, zeros are added on the left side.
For non-negative integers, shifting right by \(k\) positions is equivalent to the integer division by \(2^k\), that is, to \(\lfloor x / 2^k \rfloor\).

Example 6.32: right shift

int a = 20;  // Binary: 10100
int result = a >> 2;  // Shift right by 2 positions: 00101 (decimal: 5)

cout << "a >> 2 = " << result << endl;  // Output: 5
// Equivalent to: 20 / 2^2 = 20 / 4 = 5

Bit-by-bit operation:

						Decimal	Equivalent
`a`	1	0	1	0	0	20	\(20\)
`a > > 1`	0	1	0	1	0	10	\(20 / 2^1\)
`a > > 2`	0	0	1	0	1	5	\(20 / 2^2\)
`a > > 3`	0	0	0	1	0	2	\(\lfloor 20 / 2^3 \rfloor\)

In the last row \(20 / 2^3 = 2.5\), and the right shift gives the integer part \(2\): the bit \(1\) in position \(0\) of a > > 2 is lost.

6.10.7 Practical applications¶

The bitwise operators give short and fast solutions to common tasks. In the following examples, a mask is a number whose binary representation has the bit \(1\) only in the positions we want to act on: the mask 1 < < k has the bit \(1\) only in position \(k\).

Example 6.33: checking if a number is even or odd

int n = 15;

if (n & 1)
    cout << n << " is odd" << endl;
else
    cout << n << " is even" << endl;

// Explanation: n & 1 checks the least significant bit
// If it is 1, the number is odd; if it is 0, the number is even

Output:

15 is odd

Example 6.34: swapping two numbers without a temporary variable

int a = 5, b = 9;

cout << "Before swap: a = " << a << ", b = " << b << endl;

a = a ^ b;  // a now holds a XOR b
b = a ^ b;  // b = (a XOR b) XOR b = a
a = a ^ b;  // a = (a XOR b) XOR a = b

cout << "After swap: a = " << a << ", b = " << b << endl;

Output:

Before swap: a = 5, b = 9
After swap: a = 9, b = 5

The swap works because x x is \(0\) and x 0 is x for every integer x, and the XOR is commutative and associative.

Example 6.35: checking if a specific bit is set

int n = 12;  // Binary: 1100
int position = 2;  // Check the bit at position 2 (from right, starting at 0)

if (n & (1 << position))
    cout << "Bit " << position << " is set (1)" << endl;
else
    cout << "Bit " << position << " is not set (0)" << endl;

// Explanation: (1 << position) creates a mask with only bit at position set
// n & mask checks if that bit is 1 in n

Output:

Bit 2 is set (1)

Example 6.36: setting a specific bit to 1

int n = 12;  // Binary: 1100
int position = 1;  // Set the bit at position 1

n = n | (1 << position);  // Set bit at position 1 to 1

cout << "Result: " << n << endl;  // Output: 14 (Binary: 1110)

Example 6.37: clearing a specific bit to 0

int n = 14;  // Binary: 1110
int position = 1;  // Clear the bit at position 1

n = n & ~(1 << position);  // Set bit at position 1 to 0

cout << "Result: " << n << endl;  // Output: 12 (Binary: 1100)

The mask ~(1 < < position) has the bit \(0\) in the given position and the bit \(1\) in all the other positions.

Example 6.38: toggling a specific bit

int n = 12;  // Binary: 1100
int position = 0;  // Toggle the bit at position 0

n = n ^ (1 << position);  // Toggle bit at position 0

cout << "Result: " << n << endl;  // Output: 13 (Binary: 1101)

Key points of the chapter

A C++ program is compiled (for example with g++) and its execution starts from the main function; every instruction ends with “;”.
Every variable is declared with its data type before use; the division between two int values is the integer division.
Conditional statements (if, else, ?:) choose which instructions are executed; loops (while, for) repeat them.
The arrays of C++ are indexed from \(0\) to \(n-1\), while the arrays of the pseudo-code are indexed from \(1\) to \(n\); a dynamic-size array is allocated with new and freed with delete[].
A function receives its parameters by value (a copy) or by reference (&); an array is passed through the pointer to its first element, together with its size.
The bitwise operators act on the binary representation of the integer numbers: x < < k multiplies \(x\) by \(2^k\) and, for \(x \ge 0\), x > > k computes \(\lfloor x/2^k \rfloor\).

Exercises on this chapter: Introduction to C++

Introduction to C++¶

Introduction¶

6.1 Main characteristics of the programming language¶

6.1.1 The structure of a program¶

6.2 Variables and data types¶

6.3 Input-output stream¶

6.4 Operators¶

6.4.1 Arithmetic operators¶

6.4.2 Assignment operators¶

6.4.3 Increment and decrement operators¶

6.4.4 Relational operators¶

6.4.5 Logical operators¶

6.5 Conditional statements¶

6.5.1 Ternary operator (conditional operator)¶

6.6 Loops¶

6.6.1 The while loop¶

6.6.2 The for loop¶

6.6.3 The break and continue statements¶

6.7 Arrays¶

6.7.1 Fixed-size arrays¶

6.7.2 Dynamic-size arrays¶

6.8 The main and custom functions¶

6.8.1 Parameters passed by value and by reference¶

6.9 A complete algorithm: the maximum value in an array¶

6.10 Bitwise operators¶

6.10.1 Bitwise AND (&)¶

6.10.2 Bitwise OR (|)¶

6.10.3 Bitwise XOR ()¶

6.10.4 Bitwise NOT (~)¶

6.10.5 Left shift (< <)¶

6.10.6 Right shift (> >)¶

6.10.7 Practical applications¶

6.6.1 The `while` loop¶

6.6.2 The `for` loop¶

6.6.3 The `break` and `continue` statements¶

6.8 The `main` and custom functions¶

6.10.1 Bitwise AND (`&`)¶

6.10.2 Bitwise OR (`|`)¶

6.10.4 Bitwise NOT (`~`)¶

6.10.5 Left shift (`< <`)¶

6.10.6 Right shift (`> >`)¶