Тимофей готовится к ЕГЭ. Для отработки навыка скорости и точности поиска ответов на задания по теме «Системы счисления» ему часто приходится решать примеры типа «сколько значащих нулей (или единиц) содержит двоичная запись значения выражения $$$2^a + 2^b - 2^c$$$?». Значащими называются все цифры, кроме нулей в начале числа (которые обычно и не записываются). Например, десятичное число 20 в двоичной системе счисления записывается как 10100, и в этой записи две значащие цифры «1» и три значащие цифры «0».
Помогите Тимофею по известным $$$a$$$, $$$b$$$ и $$$c$$$ узнать ответ на задачу.
Программа получает на вход четыре целых неотрицательных числа: $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$. Числа $$$a$$$, $$$b$$$ и $$$c$$$ соответствуют показателям степеней двоек в задании $$$(0 \le a, b, c \le 10^{9})$$$. При этом гарантируется, что $$$2^a + 2^b - 2^c \gt 0$$$ и $$$a \ne b$$$.
Число $$$d$$$ равно либо $$$0$$$, либо $$$1$$$ — цифра, количество которых в значении выражения нужно узнать.
Программа должна вывести одно неотрицательное целое число — ответ на задачу.
Решение, правильно работающее в случае, когда $$$a \le 12$$$, наберет не менее 40 баллов.
4 3 2 1
2
В примере нужно узнать количество единиц в двоичной записи значения выражения $$$2^4 + 2^3 - 2^2$$$. Вычислим: $$$16 + 8 - 4 = 20$$$. $$$20_{10} = 10100_2$$$. Всего две единицы.
Такой же результат можно получить, выполнив действия в столбик, не переводя числа в десятичную систему счисления.
