Բացասական թվերը երկուական համակարգում
Մինչ այս պահը մենք խոսել ենք դրական ամբողջ թվերի մասին և այն մասին, թե ինչպես են դրանք ներկայացվում մեր համակարգիչներում։ Սակայն երբեմն անհրաժեշտ է աշխատել նաև բացասական թվերի հետ։ Ինչպե՞ս են դրանք ներկայացվում համակարգչում։
Մենք տեսանք, որ, օրինակ, 1 թիվը երկուական համակարգում ներկայացվում է որպես
0001, իսկ թիվ 6-ը՝ որպես 0110 և այլն։ 0-ն ներկայացվում է որպես զրոների հերթականություն 0000։ Տրամաբանական մի փոքր հնարք կա, որը թույլ է տալիս պահպանել բացասական թվեր․ կարելի է պահել «հատուկ» բիթ, որի արժեքը կլինի 1, եթե թիվը բացասական է, և 0՝ հակառակ դեպքում։ Դա հենց այն է, ինչ անում են համակարգիչների մեծ մասը։ Երկուական ներկայացման ամենաձախ բիթը, եթե 1 է, ապա թիվը բացասական է, իսկ եթե 0 է, ապա թիվը դրական է։Սակայն սա դեռ ամենը չէ ինչ պետք է թվի բացասական ներկայացումը ստանալու համար։ Մենք գիտենք, որ մեր սովորական (տասական) համակարգում դրական և բացասական թվերը միմյանց «չեզոքացնում» են։ Օրինակ, 6 և -6 գումարելու դեպքում ստանում ենք 0։ Նույն հատկությունը պետք է պահպանվի նաև երկուական համակարգում։ Այսինքն, եթե երկուական համակարգում գումարում ենք 6-ը և -6-ը, մենք նույնպես պետք է ստանանք 0։
Պատկերացրեք, որ ունենք 4 բիթ՝ թվի ներկայացման համար և 1 բիթ էլ նվիրված է դրական/բացասական նշանին․ այսինքն, ընդհանուր 5 բիթ։ Այդ դեպքում, 6-ը կներկայացվի որպես
00110, իսկ 0-ն՝ 00000։ -6-ի երկուական ներկայացումը պետք է «հակադարձ» լինի 6-ին, որպեսզի դրանց գումարը լինի 0։ Առաջ անցնելով ասենք, որ -6-ը կներկայացվի որպես 11010։ Իսկ եթե գումարենք 00110 և 11010, երկուական համակարգում կստանանք 00000։Դրականից բացասական և հակառակը փոխարկելու համար երկուական համակարգում կարելի է օգտվել պարզ հնարքից․ շրջել (flip) բոլոր բիթերը (0-ները դարձնել 1, իսկ 1-երը՝ 0) և ապա ստացած թվին գումարել 1։
x = 6 # 00110
x = ~x + 1 # Շրջում ենք բոլոր բիթերը և գումարում 1 => -6
x = ~x + 1 # Շրջում ենք բոլոր բիթերը և գումարում 1 => 6
z = 0 # 00000
z = ~z + 1 # Շրջել և +1 => 0
z = ~z + 1 # Շրջել և +1 => 0
z = ~z # -1 (երկուական ներկայացման մեջ բոլորը 1)
z = ~z # 0 (երկուական ներկայացման մեջ բոլորը 0)Ուշադրություն դարձրեք, որ երկուական համակարգում գումարումը կատարվում է ճիշտ այնպես, ինչպես տասական համակարգում՝ սկսելով ամենացածր կարգի նիշից (աջից) և անցում կատարելով դեպի ավելի բարձր կարգ ունեցող նիշեր (հաշվի առնելով մտքում պահված (carry) արժեքը):
Կախված ծրագրավորման լեզվից և իրականացման ձևից, համակարգիչները թվերը կարող են պահել տարբեր ձևերով։ Օրինակ, C++ և Java լեզուներում տարբեր տիպեր են օգտագործվում տարբեր տեսակներ ունեցող թվերի համար։
int տիպը պահում է 32 բիթով՝ 31 բիթը թվի համար է, իսկ ամենաառաջին բիթը համարում են նշանի բիթ։ Արդյունքում դրանք կարող են պահել -2,147,483,648 () մինչև 2,147,483,647 () միջակայքի թվեր։ Ուշադրություն դարձրեք, որ դրական թվերի առավելագույն արժեքը մեկով պակաս է, քանի որ դրական թվերը սկսվում են 0 բիթով, և այդ 0 բիթով սկսվող առաջին թիվը հենց 0-ն է (բոլոր բիթերը 0-ներ են)։Առաջադրանք
Յոթերի զարմանահրաշ երկրում ամեն բան 7 թվի հետ է կապվում։ Այնտեղի համակարգչային մասնագետները մշակել են մի համակարգ, որտեղ երկուական համակարգի թվերը (դրական և բացասական) պահվում են 77 բիթով։
Տրված է բիթ-տող
b, և ձեզ խնդրում են հաշվարկել այդ թվի բացասականը և այն ներկայացնել 77 բիթանոց համակարգում։Մուտք
Մուտքի մեջ տրված է մեկ տող, որը ներկայացնում է բիթ-տող
b (1 ≤ |b| ≤ 77)։ Այն կարող է ներկայացնել և՛ դրական, և՛ բացասական թիվ։Ելք
Ելքում պետք է տպեք մեկ տող, որը կլինի
-b արժեքը 77 բիթանոց համակարգում։Օրինակներ
Մուտք | Ելք |
1 | 11111111111111111111111111111111111111111111111111111111111111111111111111111 |
11111111111111111111111111111111111111111111111111111111111111111111111111111 | 00000000000000000000000000000000000000000000000000000000000000000000000000001 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB