Ստուգել, արդյոք տվյալ թիվը 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 ամբողջ թիվը (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