Разборы задач №2. Системы счисления

Содержание
3 – Золотая система счисления – codeforces 457A
8 – Universal convertor – informatics 749
12 – Two's complement – 1 – informatics 750
16 – Two's complement – 2 – informatics 751

Золотая система счисления – codeforces 457A

Золотая система счисления – codeforces 457A
Входные данные: две строки, в каждой из которых записана непустая строка из нулей и единиц. Длина каждой строки не превосходит 100000.
Выходные данные: «>», если первое число больше второго; «<», если первое число меньше второго; «=», если числа равны.

Золотая система счисления – codeforces 457A
Примеры

Золотая система счисления – codeforces 457A
Вспомнив правила сложения двоичных чисел, будем учитывать, что возможна замена единицы в старшем разряде на ноль с добавлением единиц в двух предшествующих разрядах без потери числа.
Тогда мы можем привести числа к одной длине и провести вычитание одного из другого. В результате мы получим число, обладающее следующими свойствами при замене единицы в старшем разряде:
Если во время замены получено 2, то уменьшаемое меньше вычитаемого.
Если во время замены получено -2, то вычитаемое меньше уменьшаемого.
Если 2 или -2 не получены, а два последних разряда равны 0, то исходные числа равны.
Если 2 или -2 не получены, а последний разряд больше 0 или последний разряд равен 0, а предпоследний больше 0, то вычитаемое меньше уменьшаемого
В иных случаях уменьшаемое меньше вычитаемого.

Золотая система счисления – codeforces 457A
#include
using namespace std;
int main() {
string a,b;
cin>>a>>b;
int n=max(a.size(),b.size());
if(a.size()
else if(b.size()
int c[100002];
for( int i=0;i
c[i]=a[i]-b[i];
}
for( int i=0;i
if(c[i]>2) {
cout<<">";
return 0;
}
if(c[i]<-2) {
cout<<"<";
return 0;
}
c[i+1]+=c[i];
c[i+2]+=c[i];
c[i]=0;
}
if(c[n-2]==0 && c[n-1]==0){
cout<<"=";
return 0;
}
if(c[n-2]>0 || (c[n-2]==0 && c[n-1]>0)) {
cout<<">";
return 0;
}
cout<<"<";
return 0;
}

Universal convertor – informatics 749

Universal convertor – informatics 749
Примеры
Для решения данной задачи достаточно сперва перевести исходное число в десятичную СЧ, а потом в целевую.

Universal convertor – informatics 749
string dex="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int to_dex(string num, int radix){
int res=0;
for (unsigned int i=1;i<=num.length();i++)
res+=dex.rfind(num[i-1])*pow(radix, num.length()-i);
return res;
}

Universal convertor – informatics 749
string to_radix(int num, int radix){
string res="";
while (num>=radix){ int x=num%radix;
res+=dex[x];
num/=radix; }
res+=dex[num];
reverse(res.begin(),res.end());
return res;}

Two's complement – 1 – informatics 750

Two's complement – 1 – informatics 750
Примеры

Two's complement – 1 – informatics 750
Поскольку числа изначально хранятся, как правило, в дополнительном коде, нам достаточно вывести n последних бит числа.
Получить i-тый бит можно так:
int bit = (x >> i) & 1;

Two's complement – 1 – informatics 750
#include
using namespace std;
int main(){
int x; cin>>x;
int n; cin>>n;
int *bits=new int[n];
for (int i=0;i
int bit = (x >> i) & 1;
bits[n-1-i]=bit; }
for (int i=0;i
cout<
return 0;}

Прыгающая лягушка – codeforces 1077A
Дана запись некоторого числа в двоичном дополнительном коде. Выведите десятичную запись этого числа.
Входные данные
Программа получает на вход строку из нулей и единиц. Длина строки не меньше 2 и не больше 16.
Выходные данные
Программа должна вывести десятичную запись числа, записанного в этой строке в двоичном дополнительном коде.

Two's complement – 1 – informatics 750
Примеры

Two's complement – 1 – informatics 750
Если число положительное, то достаточно просто получить число из входной строки.
Если же число отрицательное, то сперва нужно привести число из дополнительного кода в прямой. Для этого:
Инвертируем все биты числа (включая знаковый).
К полученному числу добавляем единицу.
Умножаем результат на -1.

Two's complement – 1 – informatics 750
Пример: перевод -5 из дополнительного кода в прямой и получение результата:
-5=1011
1) Инверсия битов: 1011->0010 (4)
2) Добавление единицы: 0100+1=0101 (5)
3) Умножение на -1: 5*(-1)=-5;