Бінарні оптимізації для щоденного використання

💡 Усі статті, обговорення, новини про Java — в одному місці. Приєднуйтесь до Java спільноти!

Привіт усім! Мене звати Максим Дудка, я Java Engineer. Сьогодні я покажу декілька простих бінарних оптимізацій, що можуть підвищити перформанс коду. На мій погляд, їхнє застосування має сенс завжди, коли це можливо з точки зору бізнес-логіки.

Статтю також можна прочитати англійською.

Побітові операції є фундаментальними інструментами у програмуванні через їхню ефективність. Основні побітові оператори:

• AND ( & ): повертає true тільки тоді, коли обидва біти дорівнюють 1.
• OR ( | ): повертає true , якщо принаймні один з бітів дорівнює 1.
• XOR ( ^ ): повертає true тільки тоді, коли 1 біт дорівнює 1, а інший — 0.
• NOT ( ~ ): змінює кожен біт (0 стає 1, а 1 стає 0).
• Лівий Зсув ( << ): зсуває біти вліво, заповнюючи праворуч нулями.
• Правий Зсув ( >> ): зсуває біти праворуч, зберігаючи знаковий біт для знакових чисел.

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

Приклади побітових операцій

Швидке множення та ділення

Клас QuickMaths демонструє використання побітових операторів лівого та правого зсуву для швидкого множення та ділення.

public class QuickMaths {

    public static int multiply(int num, int power) {

        return num << power;

    }

    public static int divide(int num, int power) {

        return num >> power;

    }

}

Пояснення роботи:

• Оператор лівого зсуву << зсуває біти числа вліво на певну кількість позицій, визначену power. Кожен зсув вліво фактично множить число на два. Наприклад, зсув на один (num << 1) подвоює число, зсув на два (num << 2) множить його на чотири й так далі. Ця операція набагато швидша, ніж звичайна операція множення, особливо для великих чисел.
• Навпаки, оператор правого зсуву >> зсуває біти числа вправо. Ця операція еквівалентна діленню числа на два для кожного зсуву. Зсув на один (num >> 1) ділить число навпіл, зсув на два (num >> 2) ділить його на чотири й так далі. Цей метод ділення, як і множення з лівим зсувом, значно швидший за традиційні методи ділення.

Перевірка числа на парність

Клас ParityCheck використовує побітову операцію AND для визначення парності числа.

public class ParityCheck {

    public static void checkParity(int num) {

        if ((num & 1) == 0) {

            System.out.println("Число парне.");

        } else {

            System.out.println("Число непарне.");

        }

    }

}

Пояснення роботи:

• Побітова операція AND порівнює кожен біт двох чисел і повертає 1 для кожної позиції біта, де обидва біти дорівнюють 1. У контексті перевірки парності числа операція num & 1 є ключовою. Ця операція порівнює найменший значущий біт числа num з 1.
• У двійковій системі всі парні числа закінчуються на 0 (наприклад, 2 — це 10, 4 — це 100), а всі непарні числа закінчуються на 1 (наприклад, 1 — це 01, 3 — це 11). Коли парне число виконує операцію AND з 1 (парне & 1), результат завжди 0, тому що найменший значущий біт парного числа — 0. Навпаки, коли непарне число виконує операцію AND з 1 (непарне & 1), результат завжди 1, тому що найменший значущий біт непарного числа — 1.
• Цей метод перевірки парності високоефективний, оскільки він містить лише одну побітову операцію, яка безпосередньо перевіряє найменший значущий біт числа. Він уникає необхідності використання операцій ділення або залишку (наприклад, num % 2), які є більш обчислювально складними.

Перевірка, чи є число степенем двійки

Клас PowerOfTwoCheck використовує побітову операцію AND для визначення, чи є число степенем двійки.

public class PowerOfTwoCheck {

    public static void isPowerOfTwo(int n) {

        if (n > 0 && (n & (n - 1)) == 0) {

            System.out.println(n + " є степенем 2.");

        } else {

            System.out.println(n + " не є степенем 2.");

        }

    }

}

Пояснення роботи:

• У двійковій формі число, що є степенем двійки, має точно один біт, встановлений у 1, а всі інші біти — у 0. Наприклад, 4 (100 у двійковому вигляді), 16 (10000 у двійковому вигляді) тощо. Ця унікальна властивість є ключем до їхньої ідентифікації.
• Вираз n & (n — 1) є центральним у цьому методі. Коли n є степенем двійки, віднімання 1 перевертає всі біти після єдиного встановленого біта (зокрема цей біт). Наприклад, 4 у двійковій системі — це 100, а 3 (що є 4-1) — це 011. Операція AND 100 & 011 дає результат 000.
• Якщо n не є степенем двійки, це означає, що в його двійковому представленні є додаткові встановлені біти, тому n & (n — 1) не буде нулем. Це тому, що віднімання 1 буде перевертати біти тільки до найменшого значущого встановленого біта, залишаючи інші встановлені біти незмінними.

Свап значеннь змінних без використання тимчасової змінної

Клас SwapVariables демонструє, як побітову операцію XOR можна використовувати для обміну значеннями двох змінних без потреби у тимчасовій змінній.

public class SwapVariables {

    public static void swap(int a, int b) {

        // Початкові значення: a = 5 (0101 у двійковому коді), b = 3 (0011 у двійковому коді)

        a = a ^ b; // a = 0101 ^ 0011 (0110 або 6 у десятковій системі)

        b = a ^ b; // b = 0110 ^ 0011 (0101 або 5 у десятковій системі, первісне значення a)

        a = a ^ b; // a = 0110 ^ 0101 (0011 або 3 у десятковій системі, первісне значення b)

        System.out.println("Після обміну: a = " + a + ", b = " + b);

    }

}

Пояснення роботи:

• XOR є побітовою операцією, яка повертає 1, тільки якщо порівнювані біти різні. Коли одне і те саме значення піддається операції XOR з самим собою, результат завжди 0 (наприклад, x ^ x = 0). Крім того, XOR є комутативною та асоціативною, що означає, що порядок операцій не змінює результат (наприклад, a ^ b ^ a те саме, що b ^ a ^ a).
• У першому кроці, a = a ^ b, a присвоюється результат XOR a та b. На цьому етапі a містить комбіновану інформацію обох a та b.
• У другому кроці, b = a ^ b, тепер b присвоюється результат XOR нового a та оригінального b. Оскільки a є a ^ b, цей крок фактично повертає a до його первісного значення, присвоюючи його b.
• У третьому кроці, a = a ^ b, a присвоюється результат XOR нового a (який є старим a ^ b) та нового b (який є оригінальним a). Цей крок фактично повертає b до його первісного значення, тепер присвоюючи його a.
• Цей метод обміну значеннями змінних не тільки елегантний, але й ефективний, оскільки уникає необхідності використання тимчасової змінної.

Знаходження унікального елементу в масиві

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

public class UniqueFinder {

    public static int findUnique(int[] array) {

        int uniqueElement = 0;

        for (int element : array) {

            uniqueElement ^= element;

        }

        return uniqueElement;

    }

}

Пояснення роботи:

• Особливістю XOR є те, що коли ви виконуєте XOR одного і того ж числа двічі, результат стає 0 (наприклад, x ^ x = 0). Ця властивість є важливою для цього методу.
• Метод findUnique ініціалізує uniqueElement до 0, а потім виконує XOR з кожним елементом масиву. У масиві, де кожен елемент, крім одного, трапляється двічі, всі елементи, що трапляються двічі, в результаті XOR дають 0, залишаючи унікальний елемент як результат. Наприклад, у масиві [2, 3, 2] розрахунок буде 0 ^ 2 ^ 3 ^ 2, що спрощується до 3, оскільки 2 ^ 2 взаємно знищується.
• Цей метод дуже ефективний, оскільки потребує лише одного проходу через масив, без потреби у вкладених циклах чи додаткових структурах даних.

Оптимізований масив булеанів (aka масив прапорців)

Клас BitwiseFlags використовує ціле число (flags) для представлення серії булевих прапорців. Кожен біт у цілому числі відповідає різному прапорцю, роблячи цей метод надзвичайно ефективним з точки зору простору, порівняно з використанням масиву boolean.

public class BitwiseFlags {

    private int flags;

    public void setFlag(int position) {

        flags |= (1 << position);

    }

    public boolean checkFlag(int position) {

        return (flags & (1 << position)) != 0;

    }

    public void clearFlag(int position) {

        flags &= ~(1 << position);

    }

}

Пояснення роботи:

• Метод setFlag використовує побітову операцію OR (|) у поєднанні з лівим зсувом (<<). Вираз (1 << position) створює значення, де тільки біт на вказаній позиції встановлено в 1. Операція OR потім забезпечує, що цей біт встановлено у зміннній flags, залишаючи інші біти незмінними.
• Для перевірки, чи встановлений певний прапорець, метод checkFlag використовує побітову операцію AND (&). Подібно до setFlag, вираз (1 << position) націлюється на конкретний біт. Якщо цей біт встановлений у flags, результат буде не нульовим (true); в іншому разі — нуль (false).
• Метод clearFlag використовує побітову операцію AND у поєднанні з побітовою операцією NOT (~). Вираз ~(1 << position) створює значення, де всі біти встановлено в 1, крім біта на вказаній позиції. Операція AND потім очищає тільки цей конкретний біт у змінній flags.
• Цей метод управління прапорцями не тільки ефективний з точки зору пам’яті, але й перформансу операцій встановлення, перевірки та очищення прапорців. Він уникає надмірного навантаження від достепу до окремих елементів масиву або об’єктів.

Висновок

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