C++: алгоритмы одной строкой

Конечно, (почти) любая аналитическая формула может быть представлена подобной однострочной функцией, поэтому суммы элементов прогрессий, площади и объёмы, выражения для расчёта физических величин и т.п. нас интересовать не будут, а только такие однострочники, которые либо показывают синтаксические особенности языка, либо демонстрируют характерные для него нетривиальные способы обращения с данными.

В отношении C++, это будут, по сути, рекурсия, побитовые операции, тернарная операция и шаблоны.

Здесь публикуются законченные консольные программки, которые проверялись в актуальной версии Visual Studio 2019. Все примеры следует расценивать больше как спорт и упражнения в красоте программирования, чем как скучные практические рекомендации. Хотя, даже при развлечении нужно помнить о том, что:

• для больших числовых значений рекурсия - не лучший подход, потому что чревата переполнением стека во время выполнения программы;
• расчёты с накоплением рассчитываемых величин в целых числах быстро дают переполнение значения, а в вещественных - погрешность результатов;
• при операциях с битами всегда следует иметь в виду sizeof (количество занимаемой памяти) для наших типов данных.

Если знаете ещё интересные функции-однострочники - пишите, я их с удовольствием опубликую.

1. Целые числа, рекурсия

1.1. Наибольший общий делитель, он же НОД или GCD.

#include <iostream>

int GCD (int a, int b) {  return b ? GCD(b, a % b) : a; }

int main() {
 std::cout << GCD(36,48); //12
 return 0;
}

1.2. Наименьшее общее кратное, оно же НОК, LCM.

#include <iostream>

int GCD (int a, int b) {  return b ? GCD(b, a % b) : a; }
int LCM (int a, int b) { return a / GCD(a, b) * b; }

int main() {
 std::cout << LCM(36,48); //144
 return 0;
}

Строго говоря, это не однострочник, так как LCM считается через CGD, но можно сделать и так:

#include <iostream>

int LCM (int a, int b) {
 return (b < 1 ? (b ? LCM(b, a % b) : a) : (a / -LCM(-b, -a % b) * b));
}

int main() {
 std::cout << LCM(36,48); //144
 return 0;
}

1.3. Факториал натурального числа.

#include <iostream>

long long unsigned fact (unsigned n) {
 return n ? n * fact(n - 1) : 1;
}

int main() {
 std::cout << fact(20); //2432902008176640000
 //на платформе x64 уже 21 даст значение больше максимально возможного 
 //для long long unsigned (18446744073709551615) и "мусор" в выводе
 return 0;
}

1.4. Сумма цифр целого числа.

#include <iostream>

int sumD (int a) {
 return (!a) ? 0 : (a % 10 + sumD(a / 10));
}

int main() {
 std::cout << sumD(12345); //15
 return 0;
}

Для отрицательного числа ответ выведется со знаком "-".

1.5. Число Фибоначчи с номером n (n == 1 для первой единицы).

#include <iostream>

int fibN (int n) {
 return (n <= 2) ? 1 : (fibN(n - 1) + fibN(n - 2));
}

int main() {
 std::cout << fibN (7); //15
 return 0;
}

1.6. Следующее число Фибоначчи (для вычисления в цикле).

#include <iostream>

int fibNext (int& n1, int& n2) {
 return n1 = (n2 += n1) - n1;
}

int main() {
 int n1 = 0, n2 = 1;
 for (int n = 0; n < 10; n++)
  std::cout << fibNext(n1,n2) << ' '; 
 //1 1 2 3 5 8 13 21 34 55
 return 0;
}

1.7. Проверка, является ли натуральное n числом Мерсенна.

#include <iostream>

bool Mersenne (unsigned  n) {
 return !(n & (n + 1));
}

int main() {
 std::cout << Mersenne(7); //1
 return 0;
}

1.8. Натуральная степень целого числа. Считает, что a0 == 1.

#include <iostream>

int pow (int a, unsigned n) { return (!n) ? 1 : a * pow(a, n - 1); }

int main() {
 std::cout << pow(-3,5); //-243
 return 0;
}

1.9. Быстрый алгоритм возведения целого числа в натуральную степень.

#include <iostream>

int pow (int a, unsigned n) {
 return (!n) ? 1 : ((n & 1) ? a : 1) * pow(a * a, n / 2);
}

int main() {
 std::cout << pow(-3, 5); //-243
 return 0;
}

В отличие от предыдущего алгоритма линейной сложности, имеет логарфмическую сложность.

2. Тернарная операция

2.1. Максимум и минимум из двух значений (шаблоны функций).

#include <iostream>

template <typename T> T max (T a, T b) {
 return (a > b) ? a : b;
}

template <typename T> T min (T a, T b) {
 return (a > b) ? b : a;
}

int main() {
 std::cout << max(-7,-3) << ' ' << min(0,4); //-3 0
 std::cout << std::endl << max(-2.5, -2.51); //-2.5
 return 0;
}

2.2. Шаблон для функции сравнения двух чисел (если a<b, вернёт отрицательное значение, если a и b равны, то ноль, иначе положительное значение.

#include <iostream>

template <typename T> int cmp (const T a, const T b) {
 return (a - b);
}

int main() {
 std::cout << cmp(-7,-3) << ' ' << cmp(1,1); //-4 0
 return 0;
}

2.3. Знак числа со значением -1, 0 или 1, шаблон функции.

#include <iostream>

template<typename T> int sign (const T& a) {
 return (a < 0 ? -1 : a > 0 ? 1 : 0);
}

int main() {
 std::cout << sign(-24) << ' ' << sign(1.5) << ' ' << sign(0.0); //-1 1 0
 return 0;
}

2.4. Найти бит с номером n (нумерация с нуля слева направо) в целочисленном массиве a. Пользуемся тем, что массив должен располагаться в последовательных адресах памяти.

#include <iostream>

int nBit (int* a, int n) {
 return (a[n >> 5] >> (n & 31)) & 1;
}

int main() {
 int a[] = {1,2,3,4,5};
 for (int i = 0; i < 32 * 5; i++) {
  std::cout << nBit(a, i);
  if (i%8 == 7) std::cout << ' ';
 }
 return 0;
}

Работает в предположении, что sizeof(int) == 4 (32 бита).

3. Операции с битами

3.1. Количество ненулевых бит в натуральном числе.

#include <iostream>

int NBit (unsigned int x) { return x == 0 ? 0 : (x & 1) + NBit(x >> 1); }

int main() {
 std::cout << NBit(12345); //6
 return 0;
}

3.2. Проверка того, является ли натуральное число степенью двойки.

#include <iostream>

bool isPow2 (unsigned int a) { return !(a & (a - 1)); }

int main() {
 std::cout << isPow2(64); //1
 return 0;
}

3.3. Обмен значений переменных a и b.

#include <iostream>

void swap (int* a, int* b) { *a ^= (*b ^= (*a ^= *b)); }

int main() {
 int a = 5, b = -3;
 swap (&a, &b);
 std::cout << a << ' ' << b; //-3 5
 return 0;
}

В реальности этот метод своппинга небезопасен даже для простых типов данных, например, не сработает swap(a,a).

Ну а для составных типов он и работать не будет, в таких случаях нужно применять std::swap.

3.4. Возведение двойки в натуральную степень n.

#include <iostream>

long long unsigned pow2 (unsigned n) {
 return 1llu << n;
}

int main() {
 std::cout << pow2(63); //9223372036854775808
  //степень 64 даст переполнение на платформе x64
 return 0;
}

3.5. Максимальная степень числа 2, на которую делится без остатка целое число n.

#include <iostream>

long long int maxDivPow2 (long long int n) {
 return n & -n;
}

int main() {
 std::cout << maxDivPow2(-24); //8
 return 0;
}

То есть, выводится именно само число (два в кубе равно восьми), а не степень двойки.

3.6. Установка в едиинцу n-ого бита числа, нумерация битов справа налево начиная с нуля, шаблон функции.

#include <iostream>

template <typename T> T setBit (T x, unsigned n) {
 return x | ((T)1 << n);
}

int main() {
 long long unsigned n = 0xfffffff0llu;
 std::cout << std::hex << setBit(n,3); //fffffff8
 return 0;
}

3.7. Обнуление n-ого бита числа, нумерация битов справа налево начиная с нуля, шаблон функции.

#include <iostream>

template <typename T> T clearBit (T x, unsigned n) {
 return x & ~((T)1 << n);
}

int main() {
 long long unsigned n = 0xffffffffllu;
 std::cout << std::hex << clearBit(n,3); //fffffff7
 return 0;
}

3.8. Переключение n-ого бита с нуля на единицу или обратно, нумерация битов справа налево начиная с нуля, шаблон функции.

#include <iostream>

template <typename T> T switchBit(T x, unsigned n) {
 return x ^ ((T)1 << n);
}

int main() {
 long long unsigned n = 0xffffffffllu;
 n = switchBit(n, 3);
 std::cout << std::hex << n << std::endl; //fffffff7
 std::cout << std::hex << switchBit(n, 3); //ffffffff
 return 0;
}

3.9. Проверка n-ого бита числа, нумерация битов справа налево начиная с нуля, шаблон функции.

#include <iostream>

template <typename T> bool checkBit(T x, unsigned n) {
 return x & ((T)1 << n);
}

int main() {
 long long unsigned n = 0x08llu;
 std::cout << std::boolalpha << checkBit(n, 3) << std::endl; //true
 std::cout << std::boolalpha << checkBit(n, 4); //false
 return 0;
}

3.10. Вернуть число, в котором установлена только самая правая единица исходного числа, нумерация битов справа налево начиная с нуля, шаблон функции.

#include <iostream>

template <typename T> T right1(T x) {
 return x & (-x);
}

int main() {
 long long n = 0xf8llu;
 std::cout << std::hex << right1(n); //8
 return 0;
}

3.11. Вернуть число, в котором установлена только единица исходного числа, соответствующая самому правому нулю, нумерация битов справа налево начиная с нуля, шаблон функции.

#include <iostream>

template <typename T> T right0(T x) {
 return ~x & (x + 1);
}

int main() {
 long long unsigned n = 0xff0fllu;
 std::cout << std::hex << right0(n); //10
 return 0;
}

3.12. Сменить самый правый нулевой бит на единичный, нумерация битов справа налево начиная с нуля, шаблон функции.

#include <iostream>

template <typename T> T setRight0(T x) {
 return x | (x + 1);
}

int main() {
 long long unsigned n = 0xff0fllu;
 std::cout << std::hex << setRight0(n); //ff1f
 return 0;
}

4. Прочее

4.1. Копирование строки с стиле Си.

Без этого однострочника не обходится нигде :) Предполагается, что строка src завершается нуль-терминатором (байтом с кодом 0x00), причём, сам он не копируется.

#include <iostream>

void copy (char* a, const char* b) {
 while (*a++ = *b++);
}

int main() {
 const char *src = "Hello";
 char dest[6] = { '\0'};
 copy (dest, src);
 std::cout << dest; //Hello
 return 0;
}

См также по теме: книгу Уоррена, можно скачать с этой страницы вместе с кодами программ из неё.

 Bit Twiddling Hacks - фундаментальное баловство с битами от Eron Anderson

12.12.2021, 16:01 [693 просмотра]