Тооны битийг шалгах, асаах, унтраах, 1 битүүдийг нь тоолох жижиг аргууд.

Pre-IntermediateХугацаа: O(1 битийн тоо)Санах ой: O(1)
HackerRank дээр бодох

Эхлээд жижиг бодлого

n = 13, k = 1 гэж өгөгдөв. 13 = 8 + 4 + 1 тул хоёртоор 1101.

1-р бит нь 0. Түүнийг асаавал 1111 = 15. Унтраавал юу ч өөрчлөгдөхгүй, 13 хэвээр. 1 бит 3 ширхэг. Хариу: 0 15 13 3.

Энгийн аргаас санаа руу

Битийг шалгах энгийн арга бол тоог 2-т дахин дахин хувааж, үлдэгдлийг нь харах. Энэ ажиллана, гэхдээ урт бөгөөд алдаа гаргахад амархан.

Компьютер битүүдтэй шууд ажилладаг >>, <<, &, |, ~ үйлдлүүдтэй. Тус бүр ганц алхам. Тэднийг хослуулбал битийг шалгах, асаах, унтраахыг нэг мөрөөр бичнэ. 1 битүүдийг тоолохдоо x &= x - 1 заль ашиглана: бүх битийг биш, зөвхөн 1 битүүдийг тойрно.

Нэр томьёо ба тэмдэглэгээ

k-р бит
Баруун талаас 0-ээс эхэлж тоолсон байрлал. 13-ыг 1101 гэж бичихэд 0-р бит нь 1, 1-р бит нь 0.
1 << k
Зөвхөн k-р бит нь 1 байх тоо, өөрөөр хэлбэл 2ᵏ. 1 << 3 = 8.
& | ~
& (AND) хоёулаа 1 бол 1, | (OR) аль нэг нь 1 бол 1, ~ (NOT) бит бүрийг эсрэгээр нь эргүүлнэ.
x & (x − 1)
x-ийн хамгийн баруун 1 битийг арилгасан тоо. 12 & 11 = 8.
cnt
1 битийн тоо. C++-д __builtin_popcount(x) ижил утга буцаана.
n = 13
0
7
0
6
0
5
0
4
1
3
1
2
0
1k
1
0
n = 13k = 1

Компьютер 13-ыг 00001101 гэж хадгална. Бит бүр 0 эсвэл 1 байна, баруун захын бит нь 0-р бит. Одоо 1-р битийг шалгаад, асаагаад, унтраая.

Алхам 1 / 8
Хурд
  • 1 бит
  • Маск
  • Шалгаж буй бит
  • Өөрчлөгдсөн бит
  • Хариу
Слайд 1 / 6

Тэг ба нэг

Компьютер тоог 0, 1 гэсэн битүүдээр хадгалдаг. 13 = 8 + 4 + 1 тул 13-ыг 1101 гэж бичнэ. Бит бүр асаах, унтраах товч шиг.

bit-manipulation.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k, cnt;
int main() {
cin >> n >> k;
int b = (n >> k) & 1;
int s = n | (1 << k);
int c = n & ~(1 << k);
int x = n;
while (x > 0) {
cnt++;
x &= x - 1;
}
cout << b << ' ' << s << ' ' << c << ' ' << cnt << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Олонлогийг ганц тоогоор хадгалах, Bitmask DP, хурдан тоолох зэрэгт хэрэглэнэ. Бит дээрх үйлдлийг компьютер хамгийн хурдан гүйцэтгэдэг.

Яаж ажилладаг вэ?

1. (n >> k) & 1: битүүдийг k байр баруун тийш шилжүүлээд хамгийн баруун битийг авна. Энэ бол k-р бит. 2. n | (1 << k): k-р битийг асаана. 1 << k гэдэг нь зөвхөн k-р бит нь 1 байх тоо. 3. n & ~(1 << k): k-р битийг унтраана. ~ бүх битийг эсрэгээр нь эргүүлнэ. 4. x &= x − 1: хамгийн баруун 1 битийг арилгана. x = 0 болтол давтахад loop 1 бит бүрт нэг л удаа эргэнэ. Оролт: n ба k. Гаралт: k-р бит, k-р битийг асаасан тоо, унтраасан тоо, 1 битийн тоо.

Яагаад зөв, хэр хурдан бэ?

x - 1 хийхэд хамгийн баруун 1 бит 0 болж, түүнээс баруун талын 0 битүүд бүгд 1 болно. Түүнээс зүүн талын битүүд өөрчлөгдөхгүй. Тиймээс x & (x - 1) яг тэр нэг битийг л арилгана. Loop 1 бит бүрт нэг удаа эргэж, x = 0 болоход зогсоно.

Шалгах, асаах, унтраах тус бүр O(1). Тоолох нь 1 битийн тоогоор эргэдэг: эерэг int-д хамгийн ихдээ 31 удаа. Сая тооны битийг тоолоход 31 сая хүрэхгүй алхам.

Түгээмэл алдаа

  • 1 << k нь int. k ≥ 31 бол overflow болно. Том тоонд 1LL << k гэж бич.
  • Үйлдлийн эрэмбэ: n & 1 << k == 0 гэвэл == эхэлж бодогдоно. Үргэлж хаалт тавь: ((n >> k) & 1) == 0.
  • ~(1 << k) нь бүх 32 битийг эргүүлдэг тул сөрөг тоо гарна. Үүнийг зөвхөн & үйлдэлтэй хамт ашигла.
  • Сөрөг x дээр while (x > 0) loop огт ажиллахгүй. Сөрөг тоонд unsigned эсвэл __builtin_popcount хэрэглэ.

Хязгаарын тохиолдол

  • n = 0: k-р бит 0, асаавал 2ᵏ, унтраавал 0, cnt = 0. Loop нэг ч эргэхгүй.
  • n = 255: 8 бит бүгд 1. Асаахад өөрчлөгдөхгүй, cnt = 8.
  • k-р бит аль хэдийн 1 бол n | (1 << k) нь n хэвээр. Аль хэдийн 0 бол n & ~(1 << k) нь n хэвээр.
  • 2-ын зэрэг, жишээ нь 64: ганц 1 бит, loop нэг л эргэнэ.

Өөрийгөө шалга

  1. 6 & 5 хэд вэ?

    Хариу харах

    4. 110 & 101 = 100.

  2. n = 10, k = 3 бол программ юу хэвлэх вэ?

    Хариу харах

    1 10 2 2. 10 = 1010 тул 3-р бит 1. Асаахад 10 хэвээр, унтраахад 2, 1 бит хоёр ширхэг.

  3. n = 200 бол x &= x - 1 loop хэдэн удаа эргэх вэ?

    Хариу харах

    3 удаа. 200-г хоёртоор бичвэл 11001000, 1 бит 3 ширхэг.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.n = 22, k = 2 бол программ юу хэвлэхийг гараар бод.

    Hint харах

    22-ыг эхлээд хоёртоор бич.

    Хариу ба тайлбар

    22 = 10110. 2-р бит 1, асаахад 22 хэвээр, унтраахад 22 − 4 = 18, 1 бит 3 ширхэг. Хариу: 1 22 18 3.

  2. 2.k-р битийг эсрэгээр нь эргүүлдэг (1 бол 0, 0 бол 1 болгодог) мөр нэм.

    Hint харах

    XOR (^) хоёр бит ялгаатай бол 1 гаргана.

    Хариу ба тайлбар

    int t = n ^ (1 << k); k-р бит эргэж, бусад нь хэвээр үлдэнэ.

  3. 3.x тэг биш бол түүний хамгийн баруун 1 битийг (жишээ нь 12-оос 4-ийг) ганц үйлдлээр ол.

    Hint харах

    Сөрөг тоо компьютерт ~x + 1 хэлбэрээр хадгалагддаг.

    Хариу ба тайлбар

    x & -x. 12 & −12 = 4. Fenwick Tree яг энэ заль дээр тулгуурладаг.

Жишээ

Оролт

13 1

Гаралт

0 15 13 3

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.