Преимущество бинарного алгоритма вычисления НОД - вместо деления используем битовую операцию сдвига вправо, которая работает быстрее деления. Битовый сдвиг вправо эквивалентен делению на 2.
Для проверки честности числа используем оператор "&" (битовый И) - выражение "!(a & 1)"
#include "stdafx.h"
#include <iostream>
using namespace std;
unsigned long long nod_bin(unsigned long long a, unsigned long long b)
{
unsigned long long d = 1;
while (a != 0 && b != 0) {
if (!(a & 1) && !(b & 1)) {
d *= 2;
a = a >> 1;
b = b >> 1;
}
else if (!(a & 1) && (b & 1)) {
a = a >> 1;
}
else if ((a & 1) && !(b & 1)) {
b = b >> 1;
}
else if ( b > a) {
int t = a;
a = (b - a) >> 1;
b = t;
}
else {
a = (a - b) >> 1;
}
}
if (a == 0) return b * d;
else if (b == 0) return a * d;
}
int _tmain(int argc, _TCHAR* argv[])
{
unsigned long long a, b;
cin >> a;
cin >> b;
cout << nod_bin(a, b) << endl;
system("pause");
return 0;
}