§ 27. Бітавыя аперацыі ў мове праграміравання
Сайт: | Профильное обучение |
Курс: | Інфарматыка. 10 клас (Павышаны ўзровень) |
Книга: | § 27. Бітавыя аперацыі ў мове праграміравання |
Напечатано:: | Гость |
Дата: | Понедельник, 29 Апрель 2024, 16:53 |
Бітавыя аперацыі таксама ляжаць у аснове камп’ютарных устройстваў, бо на іх заснавана логіка работы лагічных вентыляў — базавых элементаў лічбавых схем. Бітавыя аперацыі па сэнсе падобныя да лагічных, але ўжываюцца для кожнага разраду двайковага ўяўлення ліку (біта) асобна. Яны вызначаны толькі для цэлалікавых тыпаў і не могуць ужывацца ў дачыненні да рэчаісных лікаў. У двайковым ліку біты нумаруюцца справа налева, пачынаючы з 0. С++ падтрымлівае ўсе існыя бітавыя аперацыі. (Разгледзьце прыклад 27.1.)
Табліцы праўдзівасці бітавых і звычайных лагічных аперацый І, АБО, НЕ супадаюць. Адрозненне толькі ў тым, што бітавыя аперацыі выконваюцца над асобнымі бітамі. Відавочна, што бітавыя аператары могуць стварыць значэнні, адрозныя ад 0 ці 1. Лагічныя ж аператары заўсёды вяртаюць 0 ці 1 (прыклад 27.2). Бітавыя аператары звычайна не выкарыстоўваюцца ва ўмоўных аператарах, якімі з’яўляюцца аператары адносін і лагічныя аператары. Аператары зруху >> і << зрушваюць біты ў пераменнай управа і ўлева на вызначаны лік: пераменная >> колькасць зрухаў; агульны вягляд аператара зруху ўлева: пераменная << колькасць зрухаў; Пры пабітавым зруху біт, які выкідаецца, знікае, не ўплываючы на астатнія біты, а на месцы біта, што з’явіўся, запісваецца 0 (прыклад 27.3). Пры выкарыстанні бітавых і лагічных аперацый, а таксама аперацый параўнання неабходна ўлічваць прыярытэт іх выканання (прыклад 27.4). Области применения битовых операций:
Разгледзім выкарыстанне бітавых аперацый у С++ у дачыненні да натуральных лікаў (прыклады 27.9 — 27.16). Прыклад 27.9. Вылічыць 2n + 2m.
а) зрух адзінкі ўлева на n пазіцый; б) зрух адзінкі ўлева на m пазіцый; в) пабітавае OR з вынікамі зрухаў. Прыклад 27.10. Устанавіць i-ы біт ліку A роўным 1. Паслядоўна выконваецца:
Прыклад 27.11. Інвертаваць i-й біт ліку A. Паслядоўна выконваецца:
Прыклад 27.12. Устанавіць i-ы біт ліку A роўным 0. Паслядоўна выконваецца:
Прыклад 27.13. Абнуліць усе біты ліку A, акрамя i бітаў. Паслядоўна выконваецца:
Прыклад 27.14. Вызначыць значэнне i-га біта ліку A. Паслядоўна выконваецца:
Прыклад 27.15. Палічыць колькасць адзінак у двайковым запісе ліку A, зададзенага ў дзесятковай сістэме лічэння. Спосаб I
Спосаб II У цыкле, які паўтараем, пакуль A > 0, выконваем:
|
Прыклад 27.1. Выполнение битовых операций NOT, AND, OR, XOR.
Прыклад 27.2.
Прыклад 27.3. Выкананне аперацый пабітавага зруху.
Прыклад 27.4. Прыярытэт выканання аперацый.
Прыклад 27.5. Калі лік з’яўляецца ступенню двойкі: int z = i & (i – 1) // z = 0 Калі ў двайковым уяўленні ліку ўсе адзінкі: int z = i & (i + 1) // z = 0 Прыклад 27.6. Абнуленне крайняга правага біта ліку. A &= A - 1;
Прыклад 27.7. Абнуленне крайніх правых i біт ліку.
Прыклад 27.8. Вылічыць 2n.
Прыклад 27.9.
1) n = m = 2:
A = 8. 2) n = 2, m = 3:
Прыклад 27.10.
Прыклад 27.11. A ^= (1 << i); 1) i = 3:
2) i = 2:
Прыклад 27.12.
Прыклад 27.13.
Прыклад 27.14.
Прыклад 27.15. Вывесці значэнне 8-разраднага ліку пабітна.
Прыклад 27.16. Спосаб I.
Спосаб II.
|
Пытанні да параграфу
1. З якім тыпам даных можна выконваць бітавыя аперацыі? 2. Якія бітавыя аперацыі рэалізаваны ў С++? У чым сутнасць кожнай з іх? 3. Якія значэнні могуць быць атрыманы ў выніку выканання бітавых аперацый? 4. Якія прыярытэты выканання бітавых, лагічных аперацый і аперацый параўнання ўстаноўлены ў С++? 5. У якіх галінах дзейнасці выкарыстоўваюцца бітавыя аперацыі? |
Практыкаванні
1. Дадзены два натуральныя лікі a і b. Скласці праграму, якая рэалізуе для гэтых лікаў бітавую аперацыю па модулі два.
2. Вылічыце xor усіх лікаў на адрэзку [a, b].
3. Рэалізуйце праграмы з прыкладу 27.16. Пратэсціруйце для розных уваходных даных.
4. Дадзены лік n. Выкарыстоўваючы бітавыя аперацыі, замяніце адзінку ў малодшым разрадзе двайковага запісу ліку n на нуль.
5. Дадзены два натуральныя лікі a і n. Знайдзіце такі мінімальны натуральны лік b, што a xor b цалкам дзеліцца на n.
6. Дадзены натуральныя лікі а і k. Выведзіце лік, які складаецца толькі з k апошніх біт ліку а (гэта значыць, выкарыстоўваючы бітавыя аперацыі, абнуліце ўсе біты ліку а, акрамя апошніх k).
7. Дадзены натуральныя лікі n і k. Выкарыстоўваючы бітавыя аперацыі, абнуліце ў ліку n яго апошнія k біт і выведзіце вынік.
8. Значэннем функцыі Фенвіка для ліку n называецца максімальная ступень двойкі, на якую цалкам дзеліцца лік n. Па зададзеным ліку n вызначыце для яго значэнне функцыі Фенвіка.
9. Дадзены натуральны лік. Вызначыце, колькі разоў сустракаюцца дзве адзінкі запар (11) у двайковым уяўленні гэтага ліку (у двайковым уяўленнні 11110111 яны сустракаюцца 5 разоў).
10. Дадзены натуральны дзесятковы лік n. Памяняйце месцамі два біты з зададзенымі нумарамі ў двайковым уяўленні гэтага ліку. Напрыклад, калі n = 5 і трэба памяняць біты з нумарамі 1 і 2, то адказам будзе 3.
11. Дадзены натуральны дзесятковы лік n. Выкрасліце i-ы біт з двайковага ўяўлення гэтага ліку (малодшыя зап i-ы біт застаюцца на месцы, старшыя зрушваюцца на адзін разрад управа). Напрыклад, калі n10 = 29 (n2 = 111012)і i = 1, адказам будзе 1510 (11112).
12. Дадзены тры натуральныя лікі. Знайдзіце новы лік, кожны біт якога роўны таму значэнню, якое сустракаецца часцей сярод біт з такім жа нумарам у дадзеных лікаў.
13. Для настольнай гульні выкарыстоўваюцца карткі з нумарамі ад 1 да n (натуральны лік n не перавышае 106). Адна картка згубілася. Складзіце праграму яе пошуку. Зададзены: лік n і n - 1 номеров оставшихся карточек.
14. Дома ў Ксюшы было 2 аднолькавыя наборы кубікаў з англійскіх літар, але ў час чарговага прыбірання адзін з кубікаў згубіўся. Дапамажыце Ксюшы вызначыць, які з кубікаў адсутнічае ў адным з набораў.
15. Дадзены натуральны дзесятковы лік n. Утвараюцца ўсе магчымыя левыя цыклічныя зрухі двайковага ўяўлення ліку n, у якіх першая лічба ліку пераносіцца ў канец.
Напрыклад, калі n = 1110 (10112), то яго цыклічныя зрухі: 01112, 11102, 11012, 10112. Максімальнае значэнне m ва ўсіх атрыманых такім чынам лікаў будзе мець лік 11102 = 1410.
Складзце праграму, якая для зададзенага ліку n вызначае максімальнае значэнне m.
16. Дадзены натуральны лік n. З гэтым лікам дазваляецца неабмежаваную колькасць разоў праводзіць перастаноўку значных біт зададзенага ліку, атрымлівючы такім чынам новыя лікі. Знайдзіце найбольшую рознасць двух лікаў, кожны з якіх можна атрымаць у выніку выкананняў такіх перастановак.
17. Дадзены натуральны лік a. Напішыце выраз, вынікам якога з’яўляецца значэнне дадзенага ліку, дзе малодшы нулявы біт устаноўлены ў 1.
18. Дадзены натуральны лік a. Напішыце выраз, вынікам якога з’яўляецца пераўтварэнне дадзенага ліку ў лік, у якога ўсе біты устаноўлены ў 1, акрамя малодшага нулявога біта.