Ստուգել, արդյոք տվյալ թիվը 2-ի աստիճան է, օգտագործելով մեկ բիթային գործողություն
Տրված է դրական ամբողջ թիվ
n, և ձեզ խնդրում են պարզել, թե արդյոք այն 2-ի աստիճան է։ Սա հնարավոր է ստուգել ընդամենը մեկ բիթային գործողությամբ։ Եթե դիտարկենք 2-ի աստիճան հանդիսացող թվի երկուական ներկայացումը, այն կունենա միայն մեկ 1, իսկ մնացած բիթերը կլինեն 0-ներ։ թիվ | Երկուական համակարգի ներկայացում |
8 | 1000 |
32 | 100000 |
128 | 10000000 |
Պատահական թիվ | Երկուական համակարգի ներկայացում |
7 | 111 |
67 | 1000011 |
144 | 10010000 |
Սա նույնիսկ կարելի է հասկանալ երկուական թվերի սահմանումից: Երբ թվի ներկայացման մեջ կա ընդամենը մեկ
1, նշանակում է, որ այդ թվից «հետո» չկա այլ 2-ի աստիճան։ Ուրեմն խնդիրը կայանում է պարզելու մեջ, թե արդյոք n-ի երկուական համակարգի ներկայացման մեջ կա միայն մեկ 1։Դա կարող ենք անել բիթային
& գործողություան միջոցով, կիրառելով այն n-ի և n-1-ի վրա։ Եթե արդյունքը 0 է, նշանակում է, որ n-ը 2-ի աստիճան է։Այլ թվերի դեպքում
n & (n-1) միշտ 0 չի լինելու.- 7 & 6 = 111 & 110 = 110 (6)
- 67 & 66 = 1000011 & 1000010 = 1000010 (66)
- 144 & 143 = 10010000 & 10001111 = 10000000 (128)
Մինչդեռ 2-ի աստիճանների դեպքում այն միշտ 0 է:
- 8 & 7 = 1000 & 111 = 0
- 32 & 31 = 100000 & 11111 = 0
- 128 & 127 = 10000000 & 1111111 = 0
💡
Ինտուիցիա
Եթե նայենք
n-ի և n-1-ի բիթային ներկայացումներին, ապա ամենաբարձր կարգով բիթը (most significant bit) պահպանվում է այն դեպքում, երբ n-ի մեջ կան այլ 1-եր էլ, բացի այդ ամենաբարձրից։ Եթե n-ը 2-ի աստիճան է, ապա նրա երկուական համակարգում կա միայն մեկ 1, իսկ n-1՝ անջատում է այդ բիթը (դարձնում է 0) և մյուս բիթերը դառնում են 1։
Իսկ այնպիսի թվերի համար, ինչպիսիք են 6, 67, 144 և այլն, երկուական համակարգում առկա են մի քանի այլ 1-եր, ուստի դրանցից 1 հանելը (n-1) չի վերացնում ամենաբարձր բիթը։Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (2 ≤ n ≤ )։Ելք
Ծրագիրը ելքում պետք է տպի
Yes, եթե n-ը 2-ի աստիճան է, և No հակառակ դեպքում։Օրինակներ
Մուտք | Ելք |
8 | Yes |
17 | No |
2048 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB