Programming Basics (Part 1)

Developed by Leo V. Ivanov

Laboratory Training 4 – Use of Bitwise Operations and Arrays

Previous Next ua

Laboratory Training 4

Use of Bitwise Operations and Arrays

1 Training Tasks

1.1 Binary Representation

Write a program that reads unsigned short integers and prints their binary representation. Left-hand zeros should not be printed.

1.2 Powers of 8

Read integer value of n (from 1 to 10) and display powers of 8 from 1 to n. Use bitwise operations.

1.3 Sum of the Minimum and Maximum Items

Write a program that calculates the sum of the minimum and maximum items of an array of double precision floating point values. Use two separate functions.

1.4 Descending Order

Write a program that sorts items of an array of integers in descending order.

1.5 Individual Assignment

You should create a program that defines and initializes a two-dimensional array of integer items and then implements following activities:

  • transformation of the source array according to step one of the individual assignment
  • creation and filling of a new (one-dimensional) array of double precision floating point type items according to step two of the individual assignment
  • output of both array items

The program should signal errors if transformation or filling are not possible.

Index of variant
(from students list)		 Rule of a source array transformation (step one) Rule of filling of a new array using items of transformed source array (step two).
Resulting array should contain: 		Row count
m		 Column count
n
1
 All items with odd values should be doubled Square roots of minimal positive items of rows
4
3
2
 All items with even values should be replaced with their squares Cubic roots of minimal items of columns
3
5
3
 All items with null value should be replaced with ones Natural logarithms of maximum positive items of rows
3
4
4
 All items with even values should be doubled Natural logarithms of minimal positive items of columns
4
5
5
 All items should be replaced with their absolute magnitudes Minimal items of columns
5
4
6
 All items with even values should be tripled Cubic roots of diagonal items
3
3
7
 All positive items should be replaced with integer parts of their Briggs (base ten) logarithms Sums of negative items of columns
4
5
8
 All negative items should be replaced with their squares Square roots of diagonal items
4
4
9
 All positive items should be replaced with integer parts of their Napierian (natural) logarithms Products of negative items of rows
5
4
10
 All positive items should be replaced with integer parts of their square roots Maximum positive items of rows
3
5
11
 All positive items with even values should be doubled Cubic roots of maximum items of columns
5
4
12
 All negative items with odd values should be tripled Square roots of minimal positive items of columns
3
4
13
 All negative items with odd values should be doubled Sums of Briggs (base ten) logarithms of positive items of rows
4
3
14
 All positive items with even values should be tripled The result of division of maximal positive items of columns by their Briggs (base ten) logarithms
3
5

To calculate standard mathematical functions you should include cmath header file. Some useful functions are described below:

double sqrt(double x); Calculates the positive square root
double pow(double x, double y); Calculates x to the power of y
double log(double x); Calculates the natural logarithm of x
double log10(double x); Calculates the base ten logarithm of x.
int abs(int x); Returns the absolute value of an integer
double fabs(double x); Returns the absolute value of a floating-point number
double sin(double x); Calculates the sine of a value
double cos(double x); Calculates the cosine of a value
double atan(double x); Calculates the arc tangent

2 Instructions

2.1 Use of Bitwise Operators

C++ provides bitwise operators that act upon the individual bits. These look like, but are different from, the logical operators. The operands must be integer (preferably unsigned integer). For example

unsigned char c1 = 168;     // 10101000
unsigned char c2 =  26;     // 00011010

The AND operator (&) is a single ampersand, as opposed to the logical AND, which is two ampersands. When you apply AND to two bits, the result is 1 if both bits are 1, but 0 if either or both bits are 0:

unsigned char c3 = c1 & c2; // 00001000, or 8

The OR (|) operator is a single vertical bar, as opposed to the logical OR, which is two vertical bars. When you apply OR to two bits, the result is 1 if either bit is set or if both are:

unsigned char c4 = c1 | c2; // 10111010, or 186

The third bitwise operator is exclusive OR (^). When you apply exclusive OR to two bits, the result is 1 if the two bits are different:

unsigned char c5 = c1 ^ c2; // 10110010, or 178

The complement operator (~) clears every bit in a number that is set and sets every bit that is clear. For example:

unsigned char c6 = ~c1;     // 01010111, or 87

The SHIFT LEFT operator moves the bits to the left. This operation discards the far left bit and assigns 0 to the right most bit. For example:

unsigned char c7 = c1 << 1;  // 01010000, or 80

The SHIFT RIGHT operator moves the bits to the right. This operation discards the far right bit and assigns 0 to the left most bit. For example:

unsigned char c8 = c1 >> 2; // 00101010, or 42

You can use self assigned &=, |=, ^=, <<= and >>=.

Bitwise operations are used to work with individual bits. You can set individual bits ("flags") that are responsible for different options (instead of arrays of Boolean values). In the following example, the values of constants (flags) are consecutive powers of 2, setFlag(), removeFlag() and clearState() functions change the state of the program (global variable). The printBinary() function outputs the values in the binary notation the same way to the algorithm given in example 3.1. The program demonstrates the change and analysis of the state:

#include <iostream>

using std::cout;

const unsigned char NO_DATA = 0;
const unsigned char DATA_READ = 1;
const unsigned char SOLVED = 2;
const unsigned char ROOTS_FOUND = 4;

unsigned char state = 0;

void setFlag(unsigned char flag)
{
    state |= flag;
}

void removeFlag(unsigned char flag)
{
    state &= ~flag;
}

bool checkState(unsigned char flag)
{
    return state & flag;
}

void clearState()
{
    state = NO_DATA;
}

void printBinary(unsigned char flag)
{
    const int size = sizeof(flag) * 8;
    for (int i = 0; i < size; i++)
    {
        cout << (flag >> (size - 1));
        flag <<= 1;
    }
    cout << "\n";
}

int main()
{
    cout << "Flags:\n";
    printBinary(NO_DATA);
    printBinary(DATA_READ);
    printBinary(SOLVED);
    printBinary(ROOTS_FOUND);

    cout << "Initial state\n";
    printBinary(state);

    cout << "Data entered\n";
    setFlag(DATA_READ);
    printBinary(state);

    cout << "Data cleared\n";
    removeFlag(DATA_READ);
    printBinary(state);

    cout << "Data entered again\n";
    setFlag(DATA_READ);
    printBinary(state);

    if (checkState(DATA_READ)) {
        std::cout << "Equation was solved\n";
        setFlag(SOLVED);
        printBinary(state);
        setFlag(ROOTS_FOUND);
        printBinary(state);
    }
    std::cout << "We start first\n";
    clearState();
    printBinary(state);
    return 0;
}

The results of the program work will be as follows :

Flags:
00000000
00000001
00000010
00000100
Initial state
00000000
Data cleared
00000001
Data cleared
00000000
Data entered again
00000001
Equation was solved
00000011
00000111
We start first
00000000

Bitwise operations can be used instead of a integer multiplication and division into powers of two. Example 3.2 shows the possibility of calculating consecutive powers of 2.

2.2 Definition of One-Dimensional Arrays

An array is a collection of data storage locations, each of which holds the same type of data. Each storage location is called an item (an element) of the array.

You can declare an array by writing the type, followed by the array name and the subscript. The subscript is the number of items in the array, surrounded by square brackets. For example,

long longArray[25];

declares an array of 25 long integers, named longArray. When the compiler sees this declaration, it reserves enough memory to hold all 25 items. Because each long integer requires 4 bytes, this declaration reserves 100 contiguous bytes of memory.

You can use constants (constant expressions) to determine the size of the array. You cannot use constants that cannot be computed at compile time, as well as variables:

const int n = 10;      // explicit constant
int firstArr[n];       // OK
const int n1 = n + 3;  // constant expression
int secondArr[n1 + 2]; // OK: the size can be calculated by the compiler
// The following constant cannot be calculated by the compiler:
const int m = std::pow(3, 3) / 3;
int thirdArr[m];       // compile error
int m1 = 4;            // variable
int fourthArr[m1];     // compile error

Array items are counted from zero. Therefore, the first array item is arrayName[0]. The last index must be one less than the number of elements. For the longArray described above, this is 24.

When you write a value to an item in an array, the compiler computes where to store the value based on the size of each item and the subscript. C++ doesn't allow automatic range checking. You should implement this checking manually.

You can initialize a simple array, when you first declare this array. After the array name, you can put an equal sign (=) and a list of comma-separated values enclosed in braces. For example,

int integerArray[5] = { 1, 2, 3, 4, 5 };

declares integerArray to be an array of five integers. It assigns integerArray[0] the value 10, integerArray[1] the value 20, and so forth.

If you omit the size of the array, an array just big enough to hold the initialization is created. This definition is the same as previous one:

int integerArray[] = { 1, 2, 3, 4, 5 };

You cannot initialize more items than you've declared for the array. Therefore,

int integerArray[5] = { 1, 2, 3, 4, 5, 6 };

generates a compiler error. It is legal, however, to write

int integerArray[5] = { 1, 2 };

Although uninitialized array members have no guaranteed values, actually, aggregates will be initialized to 0. If you do not initialize an array member, its value will be set to 0.

2.3 Using Arrays

Individual items of arrays are accessed using the array subscript operator ([]). The value of the index is set using a constant, variable or expression, if it can be reduced to an integer type: 

int i = 0;
integerArray[i] = 11;
k = integerArray[2];
integerArray[k % 10 + 1] = 0;

You cannot assign one array to another. This expression generates syntax error. You should create a special cycle to copy one array into another:

const int n = 4; 
double a[n]; 
double b[n] = { 1, 2, 4, 8 };
for (int i = 0; i < n; i++)
{
    a[i] = b[i];
}

Array names can be used as actual arguments of a function. Array name without square brackets is essentially an address of the first item of an array. A copy of this address is assigned to the corresponding parameter. The function can use this address to access the array items. Changes made to the items remain in the calling function. For example,

#include <iostream>

using namespace std;

void f(double a[])
{
    a[0] = 0;
}

int main()
{
    const int n = 4;
    double a[] = { 1, 2, 4, 8 };
    int i;
    for (i = 0; i < n; i++)
    {
        cout << a[i] << ' '; //1 2 4 8
    }
    cout << endl;
    f(a);
    for (i = 0; i < n; i++)
    {
        cout << a[i] << ' '; //0 2 4 8
    }
    cout << endl;
    return 0;
}

There is no way to get the real number of array elements inside the function. Therefore, the size of the array is passed as a separate parameter:

void f(double p[], int n) { }

You cannot create an array of references, but you can declare a reference to any particular item of an array: 

double a[] = { 1, 2, 4, 8 };
double& y = a[3];
y = 16; // a[3] = 16

To iterate array items without using index, a new version of C++ language (starting from C++11) offers an alternative cycle construction: range-based for loop:

for (item_type &variable: array)
    looping_body

Within a loop body, you can use a variable as the current item of an array. For example, this way you can assign ones to all the items of an array: 

int arr[4];
for (int& k : arr)
{
    k = 1;
}

If no modification of items is provided in the body of the loop, it is better to describe a reference to a constant object:

int arr[] = { 1, 2, 3 };
for (const int &k : arr)
{
    std::cout << k << " ";
}

You cannot use an index or bypass part of an array in the body of the loop.

Unfortunately, a range-based for statement can only be used for arrays within the blocks in which those arrays are defined.

Programmers often use filling of arrays by random (pseudo-random) numbers for testing. A random number (random value) is a number whose value is not possible to calculate in advance, only we can predict the probability of getting into a certain range. The sequence of random numbers derived from one source usually have common characteristics. In programming, the most common are uniformly distributed random numbers – each value is equally likely within the range. Pseudo-random numbers commonly generated by programs, in their sequence, reproduce characteristics of random numbers, but their values are repeated each time. Such numbers can be used for debug.

In order to get random (pseudo-random) numbers in C++, you should include the cstdlib header file. The rand() function allows you to get a pseudo-random number, evenly distributed in the range of integers. To obtain numbers in a certain range, different actions are used to generated numbers, for example, finding a remainder from division.

In the above program, an array of five items is filled with pseudo-random numbers in the range of 0 to 19 inclusive:

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    const int n = 5;
    int randomArr[n];
    for (int i = 0; i < n; i++)
    {
        randomArr[i] = rand() % 20;
    }
    for (int i = 0; i < n; i++)
    {
        cout << randomArr[i] << " "; // 1 7 14 0 9
    }
    return 0;
}

After each start results will be the same.

In most cases, it is necessary to receive accidental numbers. To do this, it is necessary to initialize a generator with a certain random number, for example, the result of the function of time(0) (the ctime header file), which is the number of milliseconds that have passed from January 1, 1970. Now the program will be like that:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    const int n = 5;
    int randomArr[n];
    srand(time(0));
    for (int i = 0; i < n; i++)
    {
        randomArr[i] = rand() % 20;
    }
    for (int i = 0; i < n; i++)
    {
        cout << randomArr[i] << " "; // random numbers from 0 to 19 inclusive
    }
    return 0;
}

Random numbers should be used for testing rather than for debug.

2.4 Multidimensional Arrays

It is possible to create arrays of more than one dimension. Each dimension is represented as a subscript in the array. Therefore, a two-dimensional array has two subscripts; a three-dimensional array has three subscripts; and so on. Arrays can have any number of dimensions, however most of the arrays you create will be of one or two dimensions.

If the program contains such a definition,

// Previously, integer constants m and n were defined
double a[m][n];

the compiler will create an array of floating point numbers from m rows and n columns, which represents a rectangular table (matrix):

a[0][0]
a[0][1]
...
a[0][n - 1]
a[1][0]
a[1][1]
...
a[1][n - 1]
...
...
...
...
a[m - 1][0]
a[m - 1][1]
...
a[m - 1][n - 1]

Physically, such an array will be located in m × n sequentially arranged memory cells:

a[0][0]
a[0][1]
...
a[0][n - 1]
a[1][0]
a[1][1]
...
a[1][n - 1]
...
a[m - 1][0]
a[m - 1][1]
...
a[m - 1][n - 1]

In fact, in memory we work with a one-dimensional array. Such an array can be created explicitly:

double b[m * n];
b[i * n + j] = 0; // for a two-dimensional array a[i][j] = 0;

Using a two-dimensional array is more comfortable for the programmer.

You can initialize multidimensional arrays. You assign the list of values to array items in order, with the last array subscript changing while each of the former holds steady. Therefore, if you have an array 

int theArray[5][3];

the first three items go into theArray[0]; the next three into theArray[1]; and so forth.

You initialize this array by writing 

int theArray[5][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

For the sake of clarity, you could group the initializations with braces. For example, 

int theArray[5][3] = { { 1,  2,  3 },
                       { 4,  5,  6 },
                       { 7,  8,  9 },
                       {10, 11, 12 },
                       {13, 14, 15 } };

The compiler ignores the inner braces, which make it easier to understand how the numbers are distributed. Each value must be separated by a comma, without regard to the braces. The entire initialization set must be within braces, and it must end with a semicolon.

Only the first pair of brackets can be empty:

int theArray[][3] = { { 1,  2,  3 },
                      { 4,  5,  6 },
                      { 7,  8,  9 },
                      {10, 11, 12 },
                      {13, 14, 15 } };

In this case, compiler counts first size automatically.

There is a problem with a transferring of multidimensional arrays to the functions. In fact, it is necessary to create separate functions, clearly indicating the second, third and other dimensions (except for the first). For example:

double f(double a[][3])
{
    return a[1][1];
}

A similar approach is usually not used and bypass the problem through the use of pointers.

3 Sample Programs

3.1 Binary Representation

The following program reads unsigned short integers and prints their binary representation. The loop breaks if k is zero:

#include <iostream>

using namespace std;

void main()
{
    unsigned short int k = 1;
    while (true)
    {
        cin >> k;
        if (!k)
        {
            break;
        }
        for (int i = 0; i < 16; i++)
        {
            cout << (k >> 15);
            k <<= 1;
        }
        cout << endl;
    }
}

3.2 Powers of Two

Assume that we want to read n (from 1 to 30) and print powers of 2, from the first to the n-th power. Of course, we can use arithmetic operations, but a more effective approach that uses a bitwise shift operation will be more efficient. The program can be as follows:

#include <iostream>

using std::cin;
using std::cout;

int main()
{
    cout << "Enter n in the range from 1 to 30\n";
    int n;
    cin >> n;
    if (n < 0 || n > 30) {
        cout << "Wrong value of n\n";
    }
    else {
        for (int i = 0; i <= n; i++) {
            cout << "2 ^ " << i << " = " << (1 << i) << "\n";
        }
    }
    return 0;
}

3.3 Maximal Item

It is necessary write a program that finds maximal item of an integer array.

#include <iostream>

using namespace std;

int main()
{
    const int n = 4;
    int a[] = { 1, 2, 4, 8 };
    int indexOfMax = 0;
    for (int i = 1; i < n; i++)
    {
        if (a[i] > a[indexOfMax])
        {
            indexOfMax = i;
        }
    }
    cout << indexOfMax << ' ' << a[indexOfMax];
    return 0;
}

3.4 Sorting

It is necessary to write a program that sorts items of double array in ascending order using bubble sort algorithm.

#include<iostream>

using namespace std;

int main()
{
    const int n = 5;
    double a[] = { 11, 2.5, 4, 3, 5 };
    bool mustSort; // We must repeat sorting 
                   // if mustSort is equal true
    do
    {
        mustSort = false;
        for (int i = 0; i < n - 1; i++)
        {
            if (a[i] > a[i+1])
            // Swaps items
            {
                double temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                mustSort = true;
            }
        }
    }
    while (mustSort);
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << ' '; 
    }
    return 0;
}

3.5 Sum of Products

It is necessary write a program that declares two-dimensional array and finds the sum of products of its rows.

#include<iostream>

using namespace std;

int main()
{
    const int  m = 4;
    const int  n = 3;
    int a[][n] = { { 1, 2, 3 },
                   { 2, 3, 4 },
                   { 0, 1, 2 },
                   { 1, 1, 12} };
    int sum = 0;
    for (int i = 0; i < m; i++)
    {
        int product = 1;
        for (int j = 0; j < n; j++)
        {
            product *= a[i][j];
        }
        sum += product;
    }
    cout << sum;
    return 0;
}

3.6 Replacement

It is necessary to write a program that replaces all negative items of two-dimensional array with zeros.

#include<iostream>

using namespace std;

int main()
{
    const int  m = 3, n = 3;
    double a[][n] = { { 1,  -2,  3 },
                      { 2.1, 3, -4 },
                      { 0,-0.5, 11 } };
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] < 0)
            {
                a[i][j] = 0;
            }
        }
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << '\t' << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

3.7 Sum of Items

In the following program, sum() function returns a sum of n items of an array:

#include <iostream>

using namespace std;

double sum(double *p, int n)
{
    double s = 0;
    for (int i = 0; i < n; i++)
    {
        s += p[i];
    }
    return s;
}

int main()
{
    double a[] = {1, 2, 3, 4};
    cout << sum(a, 4) << endl; // 10;
    cout << sum(a, 3) << endl; // 6;
    return 0;
}

You can also calculate the sum of part of the array.

4 Exercises

  1. Write a program that reads unsigned short integers and prints their binary representation in reverse order.
  2. Write a program that calculates sum of positive items of an array of doubles.
  3. Write a program that defines an array of doubles and calculates sum of items with odd indices.
  4. Write a program that defines an array of integers and calculates sum of even items.
  5. Write a program that declares two-dimensional array and calculates the product of the maximal items of its columns.

5 Quiz

  1. What are the bitwise operations and how do they differ from logical?
  2. What are the bitwise operations used for?
  3. How to perform a multiplication and getting powers with bitwise operations?
  4. What is an array?
  5. What is subscript operator?
  6. What is starting index of an array?
  7. Can you use variables to determine the length of an array?
  8. Can you change the size of an array after creation?
  9. How to add a new item to the end of the array?
  10. How to transfer arrays to functions?
  11. How to get array length?
  12. How to copy values of items from one array to another?
  13. How to determine the number of columns in a two-dimensional array?
  14. How to initialize two-dimensional array?

 

Previous Next
up