Однострочники на Си/С++. Часть 2 / Хабр

Ранее я уже публиковал статью о Однострочниках на С++. Так в этом посте я хочу упомянуть ещё несколько алгоритмов, а также несколько реализаций алгоритма обмена двух чисел(с вычислением времени работы).
Всех заинтересовавшихся прошу под кат;)

1. Проверка на простоту

Для вызова этой функции надо написать prime(100, int(sqrt(100)));

bool prime(int n, int div) {
  return ( div == 1) ? true : (n % div != 0) && (prime(n, div-1));
}

Чтобы этого избежать можно создать функцию-оболочку:

bool prime(int n) {
  return ( n == 1 )? 0 : ( prime( n, int(sqrt(n))) ) ;
}

и тепер для вызова функции достаточно написать prime(100)

2. Код Грея

Кодом Грея называется такая система нумерования неотрицательных чисел, когда коды двух соседних чисел отличаются ровно в одном бите.

int codeGrey (int n) {
 return n ^ (n >> 1);
}

А также нахождение обратного кода Грея

int revCodeGrey (int g) { 
    int n;  
    for (n=0; g; n ^=g, g>>=1); 
    return n;
}

Коды Грея имеют несколько применений в различных областях:

битный код Грея соответствует гамильтонову циклу по n-мерному кубу
в решении задачи о Ханойских башнях
применение в теории генетических алгоритмов

3. Вычисление биномиального коэффициента

Биномиальный коэффициент — это коэффициент в разложении бинома Ньютона

по степеням x.

int binomialCoefficient(int k, int n) {
    return (n==k || k==0)?1:binomialCoefficient(k-1,n-1)+binomialCoefficient(k,n-1);
}

4. Нахождение степени делителя факториала

Даны два числа: [n] и [k]. Требуется посчитать, с какой степенью делитель [k] входит в число [n].

int factPow(int n, int k) {
    return (n)? (n/k + factPow(n/k, k)):0;
}

5. Возведение числа [a] в степень [b] по модулю [p].

nt powM(int a, int b, int p) {
    return b ? (a * powM(a-1, b, p) % p) : 1;
}

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

int powM(int a, int b, int p) {
    return b ? ((b&1?a:1)*powM(a*a, b/2, p) % p) : 1;
}

Мое исследование SWAPa

Вот мне пришла мысль исследовать разнообразные SWAPи, какой из них самый быстрый.
Тест SWAPов будет вот такой программкой

    int a=1, b=2;
    for(int i=0; i<=300000000; i++) {
       swap(&a, &b);
    }

где вместо swap, будут различные алгоритмы обмена двух значений.

SWAP0

Итак начнем пожалуй из STLивского, стандартного алгоритма:

template <class T> void swap0 ( T& a, T& b ) {
    T c(a); a=b; b=c;
}

его показатели были таковы:

   1,996 sec.
   1,986 sec.
   1,996 sec.

SWAP1

Следующим SWAPом будет так называемый XOR SWAP:

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

его показатели были таковы:

   3,603 sec.
   3,603 sec.
   3,608 sec.

SWAP2

void swap2(int *a, int *b) {
    *a += *b -= *a = *b - *a;
}

её показатели были таковы:

   3.728 sec.
   3.723 sec.
   3.728 sec.

SWAP3

void swap3(int *a, int *b) {
    *a /= *b = (*a= *a * (*b)) / (*b);
}

её показатели были таковы:

   7.878 sec.
   7.862 sec.
   7.862 sec.

SWAP4

void swap4(int *a, int *b) {
    *b= *a + *b - (*a = *b);
}

её показатели были таковы:

   2.012 sec.
   2.007 sec.
   2.012 sec.

SWAP5

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

её показатели были таковы:

  3.198 sec.
  3.213 sec.
  3.198 sec.

SWAP6

Ну, и ассемблерная вставка для компилятора GCC

void swap7(int *a, int *b) {
     asm volatile(
        "XOR   %%EAX,  %%EBX;      \n\t"
        "XOR   %%EBX,  %%EAX;      \n\t"
        "XOR   %%EAX,  %%EBX;      \n\t"
        :"=a"(*a),"=b"(*b)
        :"a"(*a),"b"(*b)
    );
}

её показатели были таковы:

   2.199 sec.
   2.153 sec.
   2.167 sec.

Как видим наша таблица исследований такова:

```
SWAP0 -  1.992 sec.
```
```
SWAP4 -  2.010 sec.
```
```
SWAP6 -  2.173 sec.
```
```
SWAP5 -  3.203 sec.
```
```
SWAP1 -  3.604 sec.
```
```
SWAP2 -  3.726 sec.
```
```
SWAP3 -  7.867 sec.
```