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

Битийн үйлдэл

Хоёртын тоо

Хоёртын тоо гэдэг нь 2 суурьт тооллын систем буюу хоёртын тооллын системд илэрхийлэгдсэн тоо бөгөөд энэ нь ихэвчлэн "0" (тэг) ба "1" (нэг) гэсэн хоёрхон тэмдэг ашигладаг математик илэрхийллийн арга юм.

Бит нь нэг байвал тавигдсан, тэг байвал цэвэрлэгдсэн гэж хэлнэ.

$(a_k a_{k-1} \dots a_1 a_0)_2$ хоёртын тоо нь дараах тоог илэрхийлнэ:

$$(a_k a_{k-1} \dots a_1 a_0)_2 = a_k \cdot 2^k + a_{k-1} \cdot 2^{k-1} + \dots + a_1 \cdot 2^1 + a_0 \cdot 2^0.$$

Жишээ нь $1101_2$ хоёртын тоо нь $13$ тоог илэрхийлнэ:

$$\begin{align} 1101_2 &= 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \\ &= 1\cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 13 \end{align}$$

Компьютер бүхэл тоог хоёртын тоо хэлбэрээр илэрхийлдэг. Эерэг бүхэл тоог (тэмдэгтэй ба тэмдэггүй хоёуланг) зүгээр л хоёртын цифрүүдээр нь илэрхийлдэг бол сөрөг тэмдэгтэй тоог (эерэг ба сөрөг байж болно) ихэвчлэн Хоёрын нөхөх аргаар илэрхийлдэг.

unsigned int unsigned_number = 13;
assert(unsigned_number == 0b1101);

int positive_signed_number = 13;
assert(positive_signed_number == 0b1101);

int negative_signed_number = -13;
assert(negative_signed_number == 0b1111'1111'1111'1111'1111'1111'1111'0011);

Процессор эдгээр битүүдийг тусгай үйлдлээр маш хурдан боловсруулдаг. Зарим бодлогод бид эдгээр хоёртын илэрхийллийг өөрсдийн давуу тал болгон ашиглаж, гүйцэтгэлийн хугацааг хурдасгаж болно. Мөн зарим бодлогод (ихэвчлэн комбинаторик эсвэл динамик программчлалд) өгөгдсөн объектуудын багцаас аль объектыг аль хэдийн сонгосныг хянахыг хүсэх үед бид цифр бүр нь объектыг илэрхийлэх хангалттай том бүхэл тоо ашиглаж, объектыг сонгох эсвэл орхихоос хамааран цифрийг тавьж эсвэл цэвэрлэж болно.

Битийн операторууд

Танилцуулсан эдгээр бүх оператор нь тогтмол урттай бүхэл тооны хувьд процессор дээр агшин зуурын (нэмэхтэй ижил хурдтай) байдаг.

Битийн операторууд

  • $\&$ : Битийн AND оператор нь эхний операндын бит бүрийг хоёр дахь операндын харгалзах биттэй харьцуулна. Хэрэв хоёр бит хоёулаа 1 бол харгалзах үр дүнгийн бит 1 болно. Эс бөгөөс харгалзах үр дүнгийн бит 0 болно.

  • $|$ : Битийн багтаах OR оператор нь эхний операндын бит бүрийг хоёр дахь операндын харгалзах биттэй харьцуулна. Хэрэв хоёр битийн аль нэг нь 1 бол харгалзах үр дүнгийн бит 1 болно. Эс бөгөөс харгалзах үр дүнгийн бит 0 болно.

  • $\wedge$ : Битийн үл багтаах OR (XOR) оператор нь эхний операндын бит бүрийг хоёр дахь операндын харгалзах биттэй харьцуулна. Хэрэв нэг бит 0, нөгөө бит 1 бол харгалзах үр дүнгийн бит 1 болно. Эс бөгөөс харгалзах үр дүнгийн бит 0 болно.

  • $\sim$ : Битийн нөхөх (NOT) оператор нь тооны бит бүрийг урвуулна, хэрэв бит тавигдсан бол оператор түүнийг цэвэрлэх ба цэвэрлэгдсэн бол тавина.

Жишээ:

n         = 01011000
n-1       = 01010111
--------------------
n & (n-1) = 01010000

n         = 01011000
n-1       = 01010111
--------------------
n | (n-1) = 01011111

n         = 01011000
n-1       = 01010111
--------------------
n ^ (n-1) = 00001111

n         = 01011000
--------------------
~n        = 10100111

Шилжүүлэх операторууд

Бит шилжүүлэх хоёр оператор байдаг.

  • $\gg$ Тооны сүүлийн хэдэн хоёртын цифрийг устгах замаар тоог баруун тийш шилжүүлнэ. Нэг удаагийн шилжүүлэлт бүр 2-т бүхэл тоон хуваалт хийхтэй тэнцүү тул $k$-гаар баруун шилжүүлэх нь $2^k$-д бүхэл тоон хуваалт хийхтэй тэнцүү.

    Жишээ нь $5 \gg 2 = 101_2 \gg 2 = 1_2 = 1$ бөгөөд энэ нь $\frac{5}{2^2} = \frac{5}{4} = 1$-тэй адил юм. Гэвч компьютерийн хувьд хэдэн бит шилжүүлэх нь хуваалт хийхээс хамаагүй хурдан.

  • $\ll$ Тэг цифрүүд нэмэх замаар тоог зүүн тийш шилжүүлнэ. $k$-гаар баруун шилжүүлэхтэй адилаар $k$-гаар зүүн шилжүүлэх нь $2^k$-аар үржүүлэхтэй тэнцүү.

    Жишээ нь $5 \ll 3 = 101_2 \ll 3 = 101000_2 = 40$ бөгөөд энэ нь $5 \cdot 2^3 = 5 \cdot 8 = 40$-тай адил юм.

    Гэвч тогтмол урттай бүхэл тооны хувьд энэ нь хамгийн зүүн талын цифрүүдийг хаяхыг илэрхийлэх ба хэрэв хэт их шилжүүлбэл та $0$ тоо авахад хүрнэ гэдгийг анхаараарай.

Хэрэгтэй аргууд

Бит тавих/урвуулах/цэвэрлэх

Битийн шилжүүлэлт ба зарим үндсэн битийн үйлдлийг ашиглан бид битийг амархан тавьж, урвуулж эсвэл цэвэрлэж болно. $1 \ll x$ нь зөвхөн $x$ дугаар бит нь тавигдсан тоо бол $\sim(1 \ll x)$ нь $x$ дугаар битээс бусад бүх бит нь тавигдсан тоо юм.

  • $n ~|~ (1 \ll x)$ нь $n$ тоон дахь $x$ дугаар битийг тавина
  • $n ~\wedge~ (1 \ll x)$ нь $n$ тоон дахь $x$ дугаар битийг урвуулна
  • $n ~\&~ \sim(1 \ll x)$ нь $n$ тоон дахь $x$ дугаар битийг цэвэрлэнэ

Бит тавигдсан эсэхийг шалгах

$x$ дугаар битийн утгыг тоог баруун тийш $x$ байрлалаар шилжүүлж, $x$ дугаар битийг нэгжийн байранд оруулах замаар шалгаж болох ба дараа нь 1-тэй битийн & үйлдэл хийж түүнийг гаргаж авна.

bool is_set(unsigned int number, int x) {
    return (number >> x) & 1;
}

Тоо 2-ын зэрэгт хуваагдах эсэхийг шалгах

AND үйлдлийг ашиглан бид $n$ тоо тэгш эсэхийг шалгаж болно, учир нь $n$ тэгш бол $n ~\&~ 1 = 0$, $n$ сондгой бол $n ~\&~ 1 = 1$ болно. Ерөнхийдөө $n$ нь $2^{k}$-д хуваагдах зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь $n ~\&~ (2^{k} − 1) = 0$ байх явдал юм.

bool isDivisibleByPowerOf2(int n, int k) {
    int powerOf2 = 1 << k;
    return (n & (powerOf2 - 1)) == 0;
}

Бид 1-г $k$ байрлалаар зүүн шилжүүлэх замаар $2^{k}$-г тооцоолж болно. Энэ арга ажилладгийн шалтгаан нь $2^k - 1$ нь яг $k$ нэгээс бүрдсэн тоо байдагт оршино. Мөн $2^k$-д хуваагддаг тоо тэдгээр байрлалд тэг цифртэй байх ёстой.

Бүхэл тоо 2-ын зэрэг эсэхийг шалгах

2-ын зэрэг гэдэг нь дотроо ганцхан биттэй тоо (жишээ нь $32 = 0010~0000_2$) бол түүний өмнөх тоо нь тэр цифр нь тавигдаагүй, түүний дараах бүх цифр нь тавигдсан байдаг ($31 = 0001~1111_2$). Тиймээс тоог түүний өмнөх тоотой битийн AND хийвэл үргэлж 0 гарна, учир нь тэдгээр нь ямар ч нийтлэг цифр тавигдаагүй. Энэ нь зөвхөн 2-ын зэргүүд болон аль хэдийн ямар ч цифр тавигдаагүй $0$ тооны хувьд тохиолддогийг амархан шалгаж болно.

bool isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

Баруун талын тавигдсан битийг цэвэрлэх

$n ~\&~ (n-1)$ илэрхийллийг $n$ тооны баруун талын тавигдсан битийг унтраахад ашиглаж болно. Энэ нь ажилладаг, учир нь $n-1$ илэрхийлэл нь $n$-ийн баруун талын тавигдсан битийн дараах бүх битийг, түүний дотор баруун талын тавигдсан битийг өөрийг нь урвуулдаг. Тиймээс тэдгээр бүх цифр анхны тооноос ялгаатай болох ба битийн AND хийснээр бүгд 0 болж, баруун талын тавигдсан бит нь урвуулагдсан анхны тоо $n$ гарна.

Жишээ нь $52 = 0011~0100_2$ тоог авч үзье:

n         = 00110100
n-1       = 00110011
--------------------
n & (n-1) = 00110000

Брайан Керниганы алгоритм

Дээрх илэрхийллээр бид тавигдсан битийн тоог тоолж болно.

Санаа нь бүхэл тооны баруун талын тавигдсан битийг (түүнийг тоолсны дараа) унтраах замаар зөвхөн тавигдсан битүүдийг авч үзэх бөгөөд ингэснээр давталтын дараагийн алхам дараагийн баруун талын битийг авч үзнэ.

int countSetBits(int n)
{
    int count = 0;
    while (n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}

$n$ хүртэлх тавигдсан битийг тоолох

$n$ тоо хүртэлх (түүнийг оруулаад) бүх тооны тавигдсан битийн тоог тоолохын тулд бид $n$ хүртэлх бүх тоон дээр Брайан Керниганы алгоритмыг ажиллуулж болно. Гэвч энэ нь тэмцээний илгээлтэд "Time Limit Exceeded" гаргана.

Бид $2^x$ хүртэлх тооны хувьд ($1$-ээс $2^x - 1$ хүртэл) $x \cdot 2^{x-1}$ тавигдсан бит байдаг гэсэн баримтыг ашиглаж болно. Үүнийг дараах байдлаар дүрсэлж болно. 

0 ->   0 0 0 0
1 ->   0 0 0 1
2 ->   0 0 1 0
3 ->   0 0 1 1
4 ->   0 1 0 0
5 ->   0 1 0 1
6 ->   0 1 1 0
7 ->   0 1 1 1
8 ->   1 0 0 0

Хамгийн зүүн талынхаас бусад бүх багана тус бүр $4$ (өөрөөр хэлбэл $2^2$) тавигдсан биттэй байгааг харж болно, өөрөөр хэлбэл $2^3 - 1$ тоо хүртэл тавигдсан битийн тоо нь $3 \cdot 2^{3-1}$ байна.

Шинэ мэдлэгтэй болсон бид дараах алгоритмыг гаргаж болно:

  • Өгөгдсөн тооноос бага буюу тэнцүү $2$-ын хамгийн өндөр зэргийг ол. Энэ тоог $x$ гэе.
  • $x \cdot 2^{x-1}$ томьёог ашиглан $1$-ээс $2^x - 1$ хүртэлх тавигдсан битийн тоог тооцоол.
  • $2^x$-ээс $n$ хүртэлх хамгийн их ач холбогдолтой бит дэх тавигдсан битийн тоог тоолж нэм.
  • $n$-ээс $2^x$-г хасаад шинэ $n$-ээр дээрх алхмуудыг давт.
int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            int x = std::bit_width(n) - 1;
            count += x << (x - 1);
            n -= 1 << x;
            count += n + 1;
        }
        return count;
}

Нэмэлт аргууд

  • $n ~\&~ (n + 1)$ нь араас нь дараалсан бүх нэгийг цэвэрлэнэ: $0011~0111_2 \rightarrow 0011~0000_2$.
  • $n ~|~ (n + 1)$ нь сүүлийн цэвэрлэгдсэн битийг тавина: $0011~0101_2 \rightarrow 0011~0111_2$.
  • $n ~\&~ -n$ нь сүүлийн тавигдсан битийг гаргаж авна: $0011~0100_2 \rightarrow 0000~0100_2$.

Илүү олон аргыг Hacker's Delight номноос олж болно.

Language and compiler support

C++ supports some of those operations since C++20 via the bit standard library:

  • has_single_bit: checks if the number is a power of two
  • bit_ceil / bit_floor: round up/down to the next power of two
  • rotl / rotr: rotate the bits in the number
  • countl_zero / countr_zero / countl_one / countr_one: count the leading/trailing zeros/ones
  • popcount: count the number of set bits

Additionally, there are also predefined functions in some compilers that help working with bits. E.g. GCC defines a list at Built-in Functions Provided by GCC that also work in older versions of C++:

  • __builtin_popcount(unsigned int) returns the number of set bits (__builtin_popcount(0b0001'0010'1100) == 4)
  • __builtin_ffs(int) finds the index of the first (most right) set bit (__builtin_ffs(0b0001'0010'1100) == 3)
  • __builtin_clz(unsigned int) the count of leading zeros (__builtin_clz(0b0001'0010'1100) == 23)
  • __builtin_ctz(unsigned int) the count of trailing zeros (__builtin_ctz(0b0001'0010'1100) == 2)
  • __builtin_parity(x) the parity (even or odd) of the number of ones in the bit representation

Note that some of the operations (both the C++20 functions and the Compiler Built-in ones) might be quite slow in GCC if you don't enable a specific compiler target with #pragma GCC target("popcnt").

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