Методы обработки целых чисел в программировании

Используйте битовые операции для ускорения арифметических действий. Сдвиг влево на 1 бит эквивалентен умножению на 2, а сдвиг вправо – целочисленному делению. Например, x << 3 даст результат в 8 раз больше исходного.

Проверяйте переполнение при сложении и умножении. В языках со строгой типизацией (C++, Java) выход за границы типа приводит к неопределённому поведению. Для 32-битных значений максимальное число – 2³¹-1 (2 147 483 647).

Оптимизируйте проверку чётности через & 1. Конструкция if (x & 1 == 0) работает быстрее, чем if (x % 2 == 0), так как исключает деление.

Для округления до ближайшей степени двойки примените формулу 1 << (32 - __builtin_clz(x - 1)) (GCC). Это полезно при работе с хеш-таблицами или выравнивании памяти.

Побитовые операции для оптимизации работы с числами

Используйте битовый сдвиг влево (<<) вместо умножения на степени двойки. Например, x << 3 работает быстрее, чем x * 8, и не требует вызова арифметической операции.

Для проверки чётности применяйте побитовое И (&) с единицей: (x & 1) == 0. Это исключает дорогостоящее деление с остатком.

Быстрое округление до ближайшей степени двойки:

unsigned int v = ...;
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

Замена условного ветвления при сравнении знаков:

if ((a ^ b) < 0) { ... }  // true, если знаки разные

Обмен значений без временной переменной через XOR:

x ^= y;
y ^= x;
x ^= y;

Подсчёт установленных битов (вес Хэмминга) с оптимизацией:

int count = 0;
while (n) {
n &= n - 1;
count++;
}

Контроль переполнения в арифметике

Для проверки переполнения при сложении беззнаковых значений сравнивайте результат с одним из слагаемых: если он меньше, произошло переполнение. Пример на C:

unsigned int a = UINT_MAX;
unsigned int b = 1;
unsigned int sum = a + b;
if (sum < a) {
// Обработка переполнения
}

При работе со знаковыми типами в C++ используйте встроенные проверки компилятора. Для GCC и Clang включите флаг -ftrapv, который генерирует исключение при переполнении.

В языках без встроенной защиты применяйте предварительные проверки. Для умножения:

int32_t a = INT_MAX / 2;
int32_t b = 3;
if (b > 0 && a > INT_MAX / b) {
// Переполнение неизбежно
}

В Java используйте точные операции из Math:

try {
int result = Math.addExact(x, y);
} catch (ArithmeticException e) {
// Реакция на переполнение
}

Для x86-ассемблера анализируйте флаг OF после команд ADD или IMUL. Если установлен - произошло переполнение.

В скриптовых языках (Python, JavaScript) переключитесь на длинную арифметику или используйте специальные библиотеки (например, safe-math для JS).