10931. Парность

Определим парность числа n как количество единиц в его двоичном представлении, взятую по модулю 2. Например, 21 = 10101₂ имеет 3 единицы в двоичном представлении, его парность равна 3 mod 2 = 1.

В задаче следует вычислить парность целого числа n, 1 £ n £ 2147483647.

Вход. Каждая строка содержит натуральное число n. Последняя строка содержит 0 и не обрабатывается.

Выход. Для каждого теста вывести сообщение ‘The parity of B is P (mod 2).’, где B – двоичное представление числа n, P – парность n.

Пример входа

1

2

10

21

0

Пример выхода

The parity of 1 is 1 (mod 2).

The parity of 10 is 1 (mod 2).

The parity of 1010 is 2 (mod 2).

The parity of 10101 is 3 (mod 2).

РЕШЕНИЕ

математика

Анализ алгоритма

Двоичное представление числа n ищется последовательным делением на 2. Параллельно подсчитываем количество единиц s в двоичной записи. Парность числа n равна s mod 2.

Реализация алгоритма

Двоичное представление максимального входного значения n = 2147483647 содержит не более 100 знаков. Храним его в массиве m.

char m[100];

Читаем входное значение n. Находим двоичное представление n и заносим его в символьный массив m. В переменной s подсчитываем число единиц в двоичной записи.

while(scanf("%d",&n), n)

{

memset(m,0,sizeof(m));

i = s = 0; n1 = n;

while (n > 0)

{

if (n % 2) {m[i] = '1'; s++;} else m[i] = '0';

i++;

n = n / 2;

}

Выводим двоичное представление числа n и результат s mod 2.

printf("The parity of ");

for(n = i - 1; n >= 0; n--) printf("%c",m[n]);

printf(" is %d (mod 2).\n",s);

}