Однострочники на С++

На хабе появилось несколько топиков об «однострочниках» на разных языках, которые решали простые задачи. Я решил опубликовать несколько алгоритмов на языке C/С++.
Итак, поехали!

1. Алгоритм Евклида

Рекурсивный алгоритм нахождения наибольшего общего делителя.

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

2. Нахождение НОК

Рекурсивный алгоритм нахождения наименьшего общего кратного.

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

3. Проверка числа 2^n

Алгоритм проверки числа на степень 2.

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

4. Функция обмена двух переменных

Этот алгоритм работает при помощи свойства симметричного различия, которым обладает XOR и не требует наличия третей переменой.

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

5. Алгоритм возведения в степень

Степень числа за линейное время.
Условие окончания рекурсии: если степень числа равно 0, то a^0=1.

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

6. Индийский алгоритм возведения в степень

Степень числа за логарифмическое время.

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

7. Факториал числа

Факториал целого неотрицательного числа n.
Условие продолжения рекурсии: факториал ето произведение всех натуральных чисел до n включительно.
Условие окончания рекурсии: если число равно 0, то 0!=1.

int fac(int n) {
  return n?n*fac(n-1):1;
}

8. Сумма цифр числа

Условие продолжения рекурсии: сума цифр числа равна последней цифре плюс сума цифр числа без последней цифры.
Условие окончания рекурсии: если число равно 0, то и сума цифр равна 0.

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

9. Числа Фибоначчи

Числа Фибоначчи — элементы числовой последовательности в которой каждое последующее число равно сумме двух предыдущих чисел.

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

10. Следующее число Фибоначчи

Функция нахождения чисел Фибоначчи.

int fibNext(int &f1,int &f2) {
  return f1=(f2+=f1)-f1;
}

11. Числа Мерсенна

Числа Мерсе́нна — числа вида

int Mersen(int n) {
	return !(n&(n+1));
}

12. Min & Max

int max(int a,int b) {
  return (a>b)?a:b;
}

int min(int a,int b) {
  return (a>b)?b:a;
}

13. Сравнение двух чисел

Функция возвращает значение разницы между двумя числами, поэтому если разница больше 0, то число a больше b, если равна 0, то числа одинаковы, иначе число a меньше b.

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

14. Возведение числа 2 в степень n

C помощью сдвига единицы на n битов ми вычислим двойку в степени n.

int pow2(int n) {
  return 1<<n;
}

Однострочники из коментов

Нахождение НОК от Lertmind

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

Число ненулевых битов в числе от Mrrl

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

Максимальная степень двойки, на которую делится n от Mrrl

int MaxDivPow2(int n){
  return n&-n;
}

Сравнение двух чисел от Lertmind

int cmp(int a, int b) {
    return (a < b ? -1 : (a > b ? 1 : 0));
}

или шаблон

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

Найти k-й бит в массиве int * (считая, что sizeof(int)==4) от Mrrl

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

Жду ещё алгоритмов в коментах…