Содержимое удалено Содержимое добавлено
|
|
|
==[[w:C (язык программирования)|С]]==
typedef unsigned int IntTypeInteger; /* Вместо unsigned int можно подставить любой другой целочисленный тип */ ▼Без рекурсии:
<source lang="c">
▲typedef unsigned int IntType; /* Вместо unsigned int можно подставить любой другой целочисленный тип */
IntTypeInteger gcdGCD (IntTypeInteger a, IntTypeInteger b) {
int Integer shift;
/* НОД(0, x) = x */
if (!a == 0 || b == 0)
return a | b;
/* НОД(x, 0) = x */
if (!b)
return a;
/* Вычисление shift = lg K, где K — наибольшая степень 2, на которую делятся без остатка a и b. */
for (shift = 0; !((a | b) & 1) == 0; ++shift) {
a >>= 1;
b >>= 1;
}
}
while (!(a & 1) == 0)
a >>= 1;
/* Начиная отсюда a всегда нечётно. */
do {
while (!(b & 1) == 0) /* Цикл по X */
b >>= 1;
/* Теперь a и b нечётны, поэтому их разность (diff) чётна.
Вычисление a = min(a, b), b = (a - b) / 2. */
if (a < b) {
b -= a;
} else {
a -= IntType diff(b = a - b);
a = b;
b = diff;
}
return a << shift;
}
</source>
|
