Лабораторна робота 4

Використання побітових операцій і масивів

1 Завдання на лабораторну роботу

1.1 Двійкове представлення числа

Написати програму, яка читає короткі цілі числа без знака та виводить їх двійкове представлення. Не виводити нулі на початку числа.

1.2 Степені числа 8

Увести значення n (від 0 до 10) і вивести значення степенів числа 8 до n включно. Реалізувати підхід з використанням побітових операцій.

1.3 Сума мінімального і максимального елементів

Написати програму, яка обчислює суму мінімального і максимального елементів масиву значень з плаваючою точкою подвійної точності. Здійснити пошук мінімального і максимального елементів у двох окремих функціях.

1.4 Сортування за зменшенням

Написати програму, яка сортує елементи масиву цілих чисел за зменшенням.

1.5 Індивідуальне завдання

Створити програму, яка визначає та ініціалізує двовимірний масив цілих елементів, а потім реалізує такі дії:

перетворення вихідного масиву відповідно до завдання, наведеного в колонці "Перший крок"
створення та заповнення одновимірного масиву чисел типу double відповідно до завдання, наведеного в колонці "Другий крок"
виведення на екран елементів обох масивів

Треба передбачити виведення повідомлень про помилки, якщо перетворення або заповнення неможливі.

Номер варіанту (номер студента у списку)	Перший крок Правило перетворення елементів першого масиву:	Другий крок Правило заповнення елементів другого масиву:	Кількість рядків m	Кількість стовпців n
1, 15	Усі елементи з непарними значеннями повинні бути збільшені в два рази	Квадратні корені мінімальних додатних елементів рядків	4	3
2, 16	Усі елементи з парними значеннями повинні бути замінені їх квадратами	Кубічні корені мінімальних елементів колонок	3	5
3, 17	Усі елементи з нульовим значенням слід замінити одиницями	Натуральні логарифми максимальних додатних елементів рядків	3	4
4, 18	Усі елементи з парними значеннями повинні бути збільшені в два рази	Натуральні логарифми мінімальних додатних елементів колонок	4	5
5, 19	Усі елементи повинні бути замінені їх абсолютними величинами	Мінімальні елементи колонок	5	4
6, 20	Усі елементи з парними значеннями повинні бути збільшені в три рази	Кубічні корені діагональних елементів	3	3
7, 21	Усі додатні елементи повинні бути замінені з цілими частинами їх десяткових логарифмів	Суми від'ємних елементів колонок	4	5
8, 22	Усі від'ємні елементи повинні бути замінені їх квадратами	Квадратні корені діагональних елементів	4	4
9, 23	Усі додатні елементи повинні бути замінені з цілими частинами їх натуральних логарифмів	Добутки від'ємних елементів рядків	5	4
10, 24	Усі додатні елементи повинні бути замінені з цілими частинами їх квадратних коренів	Максимальні додатні елементи рядків	3	5
11, 25	Всі додатні елементи з парними значеннями повинні бути збільшені в два рази	Кубічні корені максимальних елементів колонок	5	4
12, 26	Усі від'ємні елементи з непарними значеннями повинні бути збільшені в три рази	Квадратні корені мінімальних додатних елементів колонок	3	4
13, 27	Усі негативні елементи з непарними значеннями повинні бути збільшені в два рази	Суми десяткових логарифмів додатних елементів рядків	4	3
14, 28	Усі додатні елементи з парними значеннями повинні бути збільшені в три рази	Результати ділення максимальних додатних елементів колонок на їхні десяткові логарифми	3	5

Для виклику стандартних математичних функцій слід включити заголовний файл cmath. Деякі корисні функції описані нижче:

`double sqrt(double x);`	Обчислює квадратний корінь додатних елементів
`double pow(double x, double y);`	Обчислює x у степені y
`double log(double x);`	Обчислює натуральний логарифм x
`double log10(double x);`	Обчислює десятковий логарифм x
`int abs(int x);`	Повертає абсолютне значення цілого числа
`double fabs(double x);`	Повертає абсолютне значення числа з плаваючою точкою
`double sin(double x);`	Обчислює синус x
`double cos(double x);`	Обчислює косинус x
`double atan(double x);`	Обчислює арктангенс x

2 Методичні вказівки

2.1 Використання побітових операцій

C++ надає можливість використання так званих побітових операцій, які працюють з окремими бітами цілих чисел. Операнди повинні бути цілими числами (переважно цілі без знака). Наприклад:

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

Операція ТА (&, один амперсанд, на відміну від логічної операції), якщо її застосувати до двох бітів, повертає 1, якщо обидва біти мають значення 1, та 0, якщо один або обидва біти дорівнюють 0:

unsigned char c3 = c1 & c2; // 00001000, або 8

Операція АБО (|, одна вертикальна риска, на відміну від логічного АБО), якщо її застосувати до двох бітів, повертає 0, якщо обидва біти мають значення 0, та 1, якщо один або обидва біти дорівнюють 1:

unsigned char c4 = c1 | c2; // 10111010, або 186

Операція ВИКЛЮЧНЕ АБО (^) для двох однакових бітів встановлює результат в одиницю, якщо біти різні та нуль, якщо вони однакові:

unsigned char c5 = c1 ^ c2; // 10110010, або 178

Операція побітового заперечення, або доповнення (~) встановлює нулі в одиниці, а одиниці в нулі. Наприклад:

unsigned char c6 = ~c1;     // 01010111, або 87

Оператор << переміщує біти ліворуч. Ця операція відкидає крайній лівий біт і присвоює 0 крайньому правому біту. Наприклад:

unsigned char c7 = c1 << 1;  // 01010000, або 80

Оператор >> переміщує біти праворуч. Ця операція відкидає крайній правий біт і присвоює 0 крайньому лівому біту. Наприклад:

unsigned char c8 = c1 >> 2; // 00101010, або 42

Можна використовувати складене присвоєння: &=, |=, ^=, <<= і >>=.

Побітові операції використовують для роботи з окремими бітами числа. Можна встановлювати окремі біти числа ("прапори"), які відповідають за різні опції (замість масивів Булевих значень). В наведеному нижче прикладі значення констант (прапорів) – послідовні степені 2, функції setFlag(), removeFlag() та clearState() змінюють стан програми (глобальна змінна state). Функція printBinary() виводіть значення в двійковому вигляді вдповідно до алгоритма, наведеного в прикладі 3.1. Програма демонструє зміну та аналіз стану:

#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()
{
    setlocale(LC_ALL, "UKRAINIAN");
    cout << "Прапори:\n";
    printBinary(NO_DATA);
    printBinary(DATA_READ);
    printBinary(SOLVED);
    printBinary(ROOTS_FOUND);

    cout << "Початковий стан\n";
    printBinary(state);

    cout << "Ввели данi\n";
    setFlag(DATA_READ);
    printBinary(state);

    cout << "Очистили данi\n";
    removeFlag(DATA_READ);
    printBinary(state);

    cout << "Знову ввели данi\n";
    setFlag(DATA_READ);
    printBinary(state);

    if (checkState(DATA_READ)) {
        std::cout << "Розв'язали рiвняння\n";
        setFlag(SOLVED);
        printBinary(state);
        setFlag(ROOTS_FOUND);
        printBinary(state);
    }
    std::cout << "Починаємо спочатку\n";
    clearState();
    printBinary(state);
    return 0;
}

Результати роботи програми будуть такими:

Прапори:
00000000
00000001
00000010
00000100
Початковий стан
00000000
Ввели данi
00000001
Очистили данi
00000000
Знову ввели данi
00000001
Розв'язали рiвняння
00000011
00000111
Починаємо спочатку
00000000

Побітові операції можна використовувати замість цілого множення і ділення на степені двійки. У прикладі 3.2 продемонстровано можливість обчислення послідовних степенів 2.

2.2 Визначення одновимірних масивів

Масив – це структура даних, що складається з елементів одного типу. Всі елементи масиву займають суцільний блок пам'яті.

Масив можна створити, вказавши після змінної розмір масиву в квадратних дужках. Наприклад:

long longArray[25];

У такий спосіб ми визначили масив 25 цілих типу long int. цей масив має ім'я longArray. В нашому прикладі компілятор виділяє блок пам'яті, в якому можна розташувати 25 довгих цілих значень. Оскільки кожне довге ціле займає 4 байта, компілятор резервує 100 послідовних байтів пам'яті.

Для визначення розміру масиву можна вживати лише константи – явні або іменовані, такі які може обчислювати компілятор, а також константні вирази. Не можна використовувати константи, які не можна обчислити під час компіляції, а також змінні:

const int n = 10;      // явна константа
int firstArr[n];       // OK
const int n1 = n + 3;  // константний вираз
int secondArr[n1 + 2]; // OK: розмір може бути обчислений компілятором
// Наступна константа не може бути обчислена компілятором:
const int m = std::pow(3, 3) / 3;
int thirdArr[m];       // помилка компіляції
int m1 = 4;            // змінна
int fourthArr[m1];     // помилка компіляції

Елемент масиву можна отримати через його індекс (номер елементу). Нумерація елементів починається з 0. До першого елементу можна звернутися так: longArray[0]. Останній індекс повинен буди на одиницю менше кількості елементів. Для описаного вище масиву longArray – це 24.

Мова C++ не підтримує автоматичного контролю виходу значення індексу за межі масиву. Програміст сам повинен забезпечити цей контроль.

Під час створення масиву його можна ініціалізувати, тобто присвоїти початкові значення елементам. Список початкових значень вказують у фігурних дужках. Наприклад,

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

Ми визначили масив integerArray з п'яти цілих. Відповідні початкові значення присвоюються елементам масиву. Можна опустити розмір масиву. Тоді компілятор визначить кількість елементів зі списку початкових значень. Попереднє визначення можна було б переписати так:

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

Не можна ініціалізувати більше елементів, ніж оголошено під час його опису. Тому наведений нижче запис

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

призведе до помилки компіляції. Але, навпаки, можна написати так:

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

Решта елементів буде ініціалізована значеннями 0.

2.3 Використання одновимірних масивів

Для отримання окремого елемента масиву використовують операцію отримання індексу ([]). Значення індексу вказують за допомогою константи, змінної або виразу, якщо їх можна привести до цілого типу:

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

Не можна присвоїти один масив іншому. Це синтаксична помилка. Для копіювання елементів одного масиву в інший слід створити окремий цикл:

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];
}

Імена масивів можуть бути використані як фактичні параметри функції. Ім'я масиву без квадратних дужок є адресою першого елемента масиву. Копія цієї адреси присвоюється відповідному параметру. Функція може використовувати цю адресу для доступу до елементів масиву. Зміни, внесені в елементи, залишаються після завершення функції. Наприклад:

#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;
}

Всередині функції немає можливості отримати реальну кількість елементів масиву. Тому розмір масиву передають окремим параметром:

void f(double  p[], int  n)

Не можна створити масив посилань, але можна визначити посилання на певний елемент масиву:

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

Для перебору елементів масиву без застосування індексу нова версія C++ (починаючи з C++11) пропонує альтернативну конструкцію циклу for ("range-based for"):

for (тип_елементу &змінна: масив)
    тіло_циклу

Всередині тіла циклу можна застосовувати змінну як поточний елемент масиву. Наприклад, так можна присвоїти одиниці всім елементам масиву:

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

Якщо в тілі циклу не передбачено модифікації елементів, краще описувати посилання на константний об'єкт:

for (const int &k : arr)
{
    std::cout << k << " ";
}

В тілі циклу не можна використовувати індекс або обійти частину масиву.

На жаль цикл for, побудований на діапазоні, можна використовувати для масивів тільки всередині блоків, в яких ці масиви визначено.

З метою тестування часто використовують заповнення масивів випадковими (псевдовипадковими) числами. Випадкове число (випадкова величина, випадкове значення) – це число, значення якого неможна заздалегідь обчислити, тільки можна передбачити ймовірність потрапляння в певний діапазон. Послідовність випадкових чисел, отриманих з одного джерела, зазвичай мають спільні характеристики. У програмуванні найбільш поширеними є рівномірно розподілені випадкові числа – кожне значення однаково ймовірне у межах діапазону. Псевдовипадкові числа, які зазвичай генеруються програмами, у своїй послідовності відтворюють характеристики випадкових чисел, але їх значення кожного разу повторюються. Такі числа можна використовувати для зневадження.

Для того, щоб отримати випадкові (псевдовипадкові) числа в C++, необхідно підключити заголовний файл cstdlib. Функція rand() дозволяє отримати псевдовипадкове число, рівномірно розподілене на діапазоні цілих чисел. Для отримання чисел у певному діапазоні, до згенерованих чисел застосовують різні дії, наприклад, відшукують залишок від ділення.

У наведеній нижче програмі масив з п'яти цілих заповнюється псевдовипадковими числами у діапазоні від 0 до 19 включно:

#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;
}

Після кожного запуску результати будуть однаковими.

У більшості випадків необхідно отримувати саме випадкові числа. Для цього слід ініціалізувати генератор певним випадковим числом, наприклад, результатом функції time(0) (заголовний файл ctime), яка кількість мілісекунд, що пройшли з 1 січня 1970 року. Тепер програма буде такою:

#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] << " "; // випадкові числа від 0 до 19 включно
    }
    return 0;
}

Випадкові числа слід використовувати для тестування, а не для зневадження.

2.4 Багатовимірні масиви

Мова C++ дозволяє створювати масиви з більш ніж одним виміром. Кожен вимір представлено як окремий індекс масиву. Масиви можуть мати будь-яке число вимірів, однак найчастіше створюють одновимірні і двовимірні масиви. Двовимірний масив можна представити як прямокутну таблицю. Тоді перший індекс найчастіше пов'язують з номером рядку, а другий – з номером стовпця.

Якщо в програмі буде таке визначення,

// Раніше були визначені цілі константи m і n
double a[m][n];

компілятор створить масив дійсних чисел з m рядків і n стовпців, який представляє прямокутну таблицю (матрицю):

`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]`

Фізично такий масив буде розташовано в m × n послідовно розташованих комірках пам'яті:

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]

Фактично в пам'яті ми працюємо з одновимірним масивом. Такий масив можна створити явно:

double b[m * n];
b[i * n + j] = 0; // для двовимірного масиву a[i][j] = 0;

Використання двовимірного масиву більш зручне для програміста.

Багатовимірні масиви також можна ініціалізувати. Наприклад:

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

Це означає, що перші три елементи записують в рядок з індексом 0, наступні 3 – в рядок з індексом 1 тощо.

Для більшої наочності елементи можна згрупувати вкладеними дужками. Наприклад,

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

Компілятор ігнорує внутрішні фігурні дужки. Їх використовують тільки для того, щоб краще зрозуміти, як значення розділені. Значення повинні бути розділені комою, без урахування дужок. Весь набір ініціалізації повинен бути взятий у фігурні дужки і повинен закінчуватися крапкою з комою.

Тільки перша пара дужок може бути порожньою:

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

В цьому випадку компілятор обчислює перший розмір автоматично.

Існує проблема з передачею в функції багатовимірних масивів. Фактично необхідно створювати окремі функції, явно вказуючи другу, третю та інші розмірності (окрім першої), наприклад:

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

Подібний підхід зазвичай не використовують і обходять проблему через використання вказівників.

3 Приклади програм

3.1 Двійкове представлення числа

Наведена нижче програма зчитує короткі цілі числа без знака і виводить їх двійкове представлення. Цикл переривається, якщо k дорівнює нулю:

#include <iostream>

using namespace std;

int 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;
    }
    return 0;
}

3.2 Степені числа 2

Необхідно ввести n (1 до 30 включно) та вивести на екран степені числа 2 – від першого до введеного n-го. Звичайно, можна скористатися арифметичними операціями, але більш ефективним буде підхід, який використовує побітову операцію зсуву. Програма буде такою:

#include <iostream>

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

int main()
{
    setlocale(LC_ALL, "UKRAINIAN");
    cout << "Уведiть n у дiапазонi вiд 1 до 30\n";
    int n;
    cin >> n;
    if (n < 0 || n > 30) {
        cout << "Неправильне значення n\n";
    }
    else {
        for (int i = 0; i <= n; i++) {
            cout << "2 ^ " << i << " = " << (1 << i) << "\n";
        }
    }
    return 0;
}

3.3 Максимальний елемент

Наведена нижче програма знаходить максимальний елемент масиву цілих.

#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 Сортування

Наведена нижче програма сортує елементи масиву в порядку зростання, використовуючи алгоритм сортування бульбашкою.

#include<iostream>

using namespace std;  

int main()
{
    const int n = 5;
    double a[] = { 11, 2.5, 4, 3, 5 };
    bool mustSort; // повторюємо сортування 
                   // якщо mustSort дорівнює true
    do
    {
        mustSort = false;
        for (int i = 0; i < n - 1; i++)
        {
            if (a[i] > a[i+1])
            // Обмінюємо елементи
            {
                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 Сума добутків

У наведеній нижче програмі визначено двовимірний масив і здійснюється знаходження суми добутків його рядків.

#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 Заміна

У наведеній нижче програмі здійснюється заміна від'ємних елементів двовимірного масиву нулями.

#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() обчислює і повертає суму елементів масиву:

#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;
}

4 Вправи для контролю

Написати програму, яка читає короткі цілі числа без знака та виводить їх двійкове представлення у зворотному порядку.
Написати програму, яка обчислює суму додатних елементів масиву дійсних чисел.
Написати програму, яка визначає масив дійсних чисел і обчислює суму елементів з непарними індексами.
Написати програму, яка визначає масив цілих чисел і обчислює суму парних елементів.
Написати програму, яка визначає двовимірний масив і обчислює добуток максимальних елементів його стовпців.

5 Контрольні запитання

Які є побітові операції та чим вони відрізняються від логічних?
Для чого використовують побітові операції?
Як за допомогою побітових операцій здійснювати множення та піднесення у степінь?
Що таке масив?
Що таке оператор індексування?
Яким є стартовий індекс масиву?
Чи можна використовувати змінні для визначення довжини масиву?
Як змінити розмір масиву після створення?
Як додати новий елемент в кінець масиву?
Як здійснюється передача масивів у функції?
Як отримати довжину масиву?
Як скопіювати значення елементів з одного масиву в інший?
Як визначити кількість стовпців в двовимірному масиві?
Як ініціалізувати двовимірний масив?

Попередня Наступна

Основи програмування (частина 1)

Розробник курсу Л. В. Іванов

Лабораторна робота 4 – Використання побітових операцій і масивів