Агуулгыг алгасах

Дэд маск тоолох

Өгөгдсөн маскийн бүх дэд маскийг тоолох

Битмаск $m$ өгөгдсөн үед та түүний бүх дэд маскийг, өөрөөр хэлбэл зөвхөн $m$ маскт багтсан битүүд нь тавигдсан $s$ маскуудыг үр ашигтай давтахыг хүсэж байна.

Битийн үйлдлийн аргад тулгуурласан энэ алгоритмын хэрэгжүүлэлтийг авч үзье:

int s = m;
while (s > 0) {
 ... you can use s ...
 s = (s-1) & m;
}

or, using a more compact for statement:

for (int s=m; s; s=(s-1)&m)
 ... you can use s ...

In both variants of the code, the submask equal to zero will not be processed. We can either process it outside the loop, or use a less elegant design, for example:

for (int s=m; ; s=(s-1)&m) {
 ... you can use s ...
 if (s==0)  break;
}

Дээрх код яагаад $m$-ийн бүх дэд маскийг давталтгүйгээр, буурах эрэмбээр давдгийг судалъя.

Бидэнд одоогийн битмаск $s$ байгаа бөгөөд бид дараагийн битмаск руу шилжихийг хүсэж байна гэж үзье. $s$ маскаас нэгжийг хасснаар бид баруун талын тавигдсан битийг устгах ба түүний баруун талын бүх бит 1 болно. Дараа нь бид $m$ маскт багтаагүй, улмаар дэд маскийн хэсэг байж чадахгүй бүх "илүү" нэг битийг устгана. Энэ устгалыг бид (s-1) & m битийн үйлдлээр хийнэ. Үр дүнд нь бид $s-1$ маскийг "тайрч", түүний авч болох хамгийн их утгыг, өөрөөр хэлбэл буурах эрэмбээр $s$-ийн дараах дэд маскийг тодорхойлно.

Тиймээс энэ алгоритм давталт тутамд ердөө хоёр үйлдэл хийж, энэ маскийн бүх дэд маскийг буурах эрэмбээр үүсгэнэ.

Тусгай тохиолдол бол $s = 0$ үе юм. $s-1$-г гүйцэтгэсний дараа бид бүх бит тавигдсан маск (-1-ийн битийн илэрхийлэл) авах ба (s-1) & m-ийн дараа $s$ нь $m$-тэй тэнцүү болно. Тиймээс $s = 0$ маскийн хувьд болгоомжтой байгаарай — хэрэв давталт тэг дээр дуусахгүй бол алгоритм төгсгөлгүй давталтад орж болзошгүй.

Бүх маск ба тэдгээрийн дэд маскийг давтах. Complexity $O(3^n)$

Олон бодлогод, ялангуяа битмаск динамик программчлал ашигладаг бодлогод та бүх битмаскийг давтаж, маск бүрийн хувьд түүний бүх дэд маскийг давтахыг хүсдэг:

for (int m=0; m<(1<<n); ++m)
    for (int s=m; s; s=(s-1)&m)
 ... s and m ...

Дотоод давталт нийт $O(3^n)$ удаа гүйцэтгэгдэхийг баталъя.

Эхний баталгаа: $i$ дугаар битийг авч үзье. Түүнд яг гурван сонголт бий:

  1. энэ нь $m$ маскт багтаагүй (улмаар $s$ дэд маскт ч багтаагүй),
  2. энэ нь $m$-д багтсан боловч $s$-д багтаагүй, эсвэл
  3. энэ нь $m$ ба $s$ хоёуланд нь багтсан.

Нийт $n$ бит байдаг тул $3^n$ өөр хослол байна.

Хоёр дахь баталгаа: Хэрэв $m$ маск $k$ идэвхжсэн биттэй бол түүнд $2^k$ дэд маск байхыг анхаараарай. Бидэнд $k$ идэвхжсэн биттэй нийт $\binom{n}{k}$ маск байгаа тул (биномын коэффициент-ийг үзнэ үү) бүх маскийн хослолын нийт тоо нь:

$$\sum_{k=0}^n \binom{n}{k} \cdot 2^k$$

Энэ тоог тооцоолохын тулд дээрх нийлбэр нь биномын теоремоор $(1+2)^n$-ийн задаргаатай тэнцүү болохыг анхаараарай. Тиймээс бид батлахыг хүссэнчлэн $3^n$ хослолтой болно.

Дасгал бодлогууд