Các phép toán thao tác Bit

Thao tác bit là các phép toán một ngôi và hai ngôi trên biểu diễn nhị phân của số nguyên, chia thành phép toán bit và dịch bit．Đây là nhóm phép toán cơ bản nhất của CPU, tốc độ thường rất nhanh．

Số nguyên và dãy bit

Tham khảo thêm: Kiểu số nguyên

Chúng ta gọi một dãy độ dài cố định chỉ gồm 0 hoặc 1 là dãy bit．Bit ngoài cùng bên trái gọi là bit cao nhất, bit ngoài cùng bên phải gọi là bit thấp nhất．

Máy tính dùng dãy bit để biểu diễn số nguyên trong một phạm vi nhất định．Với độ dài \(N\), dãy bit chỉ có \(2^N\) khả năng, nên chỉ có thể thiết lập quan hệ một-một với \(2^N\) số nguyên．Quan hệ một-một này chia làm hai loại: có dấu và không dấu．Có dấu nghĩa là tập số tương ứng có số âm, không dấu nghĩa là tất cả đều không âm．

Với quan hệ không dấu, ta có thể trực tiếp dùng biểu diễn nhị phân của số nguyên làm dãy bit, thiếu độ dài thì thêm 0 ở bit cao．

Trong quan hệ không dấu, dãy bit độ dài \(N\) biểu diễn các số trong \([0,2^N-1]\)．
Với quan hệ có dấu, có hai quy tắc biểu diễn: mã bù 1 (ones' complement) và mã bù 2 (two's complement)．

Với số không âm, quy tắc biểu diễn giống không dấu; với số âm, lấy dãy bit ứng với trị tuyệt đối rồi đảo bit (đổi 0 thành 1, 1 thành 0) gọi là mã bù 1; lấy mã bù 1 theo quan hệ không dấu đổi sang số nguyên rồi cộng một, cuối cùng đổi về dãy bit theo quan hệ không dấu, bỏ phần vượt quá độ dài ban đầu, thu được mã bù 2．

Trong quan hệ mã bù 1, dãy bit độ dài \(N\) biểu diễn các số trong \([-2^{N-1}+1,2^{N-1}-1]\)．

Trong quan hệ mã bù 2, dãy bit độ dài \(N\) biểu diễn các số trong \([-2^{N-1},2^{N-1}-1]\)．

Lấy dãy bit \(3\) bit làm ví dụ:

Dãy bit	Số không dấu	Số có dấu (mã bù 1)	Số có dấu (mã bù 2)
`000`	\(0\)	\(0\)	\(0\)
`001`	\(1\)	\(1\)	\(1\)
`010`	\(2\)	\(2\)	\(2\)
`011`	\(3\)	\(3\)	\(3\)
`100`	\(4\)	\(-3\)	\(-4\)
`101`	\(5\)	\(-2\)	\(-3\)
`110`	\(6\)	\(-1\)	\(-2\)
`111`	\(7\)	\(-0\)	\(-1\)

Có thể thấy vấn đề lớn nhất của mã bù 1 là xuất hiện \(-0\) (không tồn tại trong thực tế), vì vậy thông thường ta chỉ dùng mã bù 2．Do khi biểu diễn số có dấu, dấu của số chỉ do bit cao nhất quyết định, nên bit này gọi là bit dấu．

Đổi dãy bit sang số nguyên cũng khá dễ: với số không âm thì không cần xử lý đặc biệt; với mã bù 1 thì đảo bit để lấy số đối; với mã bù 2 thì đảo bit rồi cộng một để lấy số đối．

Phép toán bit

Phép toán bit là việc áp dụng từng bit một số hàm Boolean．Về hình thức, với hàm Boolean \(f:\mathbf{B}^k\to \mathbf{B}\), phép toán bit là hàm dạng

\[ \begin{aligned} F:\left(\mathbf{B}^m\right)^k&\to \mathbf{B}^m\\ ((p_{1,1},\dots,p_{m,1}),\dots,(p_{1,k},\dots,p_{m,k}))&\mapsto (f(p_{1,1},\dots,p_{1,k}),\dots,f(p_{m,1},\dots,p_{m,k})) \end{aligned} \]

trong đó \(m\) là độ dài dãy bit．Tương tự, ta thường chỉ nghiên cứu phép toán bit một ngôi và hai ngôi．Nếu không nói rõ, các phép toán bit dưới đây đều chỉ xét một ngôi và hai ngôi．

Thông thường, ta coi đảo bit, AND, OR, XOR là các phép toán bit cơ bản, còn các phép khác đều có thể tổ hợp từ chúng．

Phép toán bit	Ký hiệu toán học	Hàm Boolean tương ứng	Toán tử C++	Diễn giải
Đảo bit	\(\operatorname{NOT}\)	\(\lnot\)	`~`	Đổi \(0\) thành \(1\), \(1\) thành \(0\)
AND	\(\operatorname{AND}\)	\(\land\)	`&`	Chỉ khi cả hai bit đều \(1\) thì là \(1\)
OR	\(\operatorname{OR}\)	\(\lor\)	`\|`	Chỉ cần một trong hai bit là \(1\) thì là \(1\)
XOR	\(\oplus\)、\(\operatorname{XOR}\)	\(\oplus\)	`^`	Chỉ khi hai bit khác nhau thì là \(1\)

Warning

Lưu ý phân biệt phép toán bit và hàm Boolean．

Ví dụ:

\(\operatorname{NOT} 01010111=10101000\)，
\(01010011 \operatorname{AND} 00110010=00010010\)，
\(01010011 \operatorname{OR} 00110010=01110011\)，
\(01010011 \operatorname{XOR} 00110010=01100001\)．

Do bốn phép toán trên thao tác độc lập trên từng bit, nên chúng trực tiếp kế thừa các tính chất của hàm Boolean tương ứng．

Để tiện, khi độ dài dãy bit đã biết, ta cũng có thể thao tác trực tiếp trên số nguyên, ví dụ:

\[ \begin{aligned} \operatorname{NOT} 5&=-6,\\ \operatorname{NOT} (-5)&=4,\\ 5 \operatorname{AND} 6 &=4,\\ 5 \operatorname{OR} 6 &=7,\\ 5 \operatorname{XOR} 6 &=3. \end{aligned} \]

Giả sử \(x,y\geq 0\), ta cũng có thể biểu diễn phép toán bit dưới dạng tổng:

\[ \begin{aligned} \operatorname{NOT} x&=\sum_{n=0}^{\lfloor\log_{2}x\rfloor}2^n\left(\left(\left\lfloor\frac{x}{2^n}\right\rfloor\bmod 2+1\right)\bmod 2\right)\\ &=\sum_{n=0}^{\lfloor\log_{2}x\rfloor}\left(2^{\left\lfloor\log_{2}x\right\rfloor +1}-1-x\right)\\ x\operatorname{AND} y&=\sum_{n=0}^{\lfloor\log_{2}\max\{x,y\}\rfloor}2^n\left(\left\lfloor\frac{x}{2^n}\right\rfloor\bmod 2\right)\left(\left\lfloor{\frac{y}{2^n}}\right\rfloor\bmod 2\right)\\ x\operatorname{OR} y&=\sum_{n=0}^{\lfloor\log_{2}\max\{x,y\}\rfloor}2^n\left(\left(\left\lfloor\frac{x}{2^n}\right\rfloor\bmod 2\right)+\left(\left\lfloor{\frac{y}{2^n}}\right\rfloor\bmod 2\right)-\left(\left\lfloor\frac{x}{2^n}\right\rfloor\bmod 2\right)\left(\left\lfloor{\frac{y}{2^n}}\right\rfloor\bmod 2\right)\right)\\ x\operatorname{XOR} y&=\sum_{n=0}^{\lfloor\log_{2}\max\{x,y\}\rfloor}2^n\left(\left(\left(\left\lfloor\frac{x}{2^n}\right\rfloor\bmod 2\right)+\left(\left\lfloor{\frac{y}{2^n}}\right\rfloor\bmod 2\right)\right)\bmod 2\right)\\ &=\sum_{n=0}^{\lfloor\log_{2}\max\{x,y\}\rfloor}2^n\left(\left(\left\lfloor\frac{x}{2^n}\right\rfloor +\left\lfloor\frac{y}{2^n}\right\rfloor\right)\bmod 2\right) \end{aligned} \]

Khi không gây nhầm lẫn, phần sau sẽ lược bỏ chữ “theo bit”．

Dịch bit

Tham khảo thêm: Toán tử bit trong C++．

Dịch bit là phép toán hai ngôi dịch dãy bit sang trái hoặc phải, tham số thứ nhất là dãy bit, tham số thứ hai thường là số nguyên không âm．Dịch sang trái gọi là dịch trái, dịch sang phải gọi là dịch phải．Tùy cách điền các bit trống sau khi dịch, có thể chia thành dịch số học, dịch логic, dịch vòng．Trong đó

Dịch логic điền 0 vào chỗ trống，
Dịch phải số học điền bit dấu vào chỗ trống; dịch trái số học giống dịch trái логic，
Dịch vòng điền các bit tràn vào chỗ trống．

Ví dụ với dãy 8 bit 10 01 01 10：

Thao tác	Kết quả
Dịch trái số học 2 bit	`01 01 10 00`
Dịch phải số học 2 bit	`11 10 01 01`
Dịch trái логic 2 bit	`01 01 10 00`
Dịch phải логic 2 bit	`00 10 01 01`
Dịch vòng trái 2 bit	`01 01 10 10`
Dịch vòng phải 2 bit	`10 10 01 01`

Trong C++, dùng a << b cho dịch trái, a >> b cho dịch phải; quy tắc cụ thể xem Toán tử bit trong C++．

Ta có thể dùng đoạn code sau để реализовать dịch vòng:

实现

// From <https://stackoverflow.com/a/776523/224132>
#include <climits>
#include <cstdint>

uint32_t rotl32(uint32_t value, unsigned int count) {
  const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
  count &= mask;
  return (value << count) | (value >> (-count & mask));
}

uint32_t rotr32(uint32_t value, unsigned int count) {
  const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
  count &= mask;
  return (value >> count) | (value << (-count & mask));
}

Ứng dụng của thao tác bit

Thao tác bit thường có ba tác dụng:

Thực hiện một số phép tính hiệu quả, thay cho cách làm kém hiệu quả．Tham khảo Tối ưu biên dịch #Giảm cường độ．
Biểu diễn tập hợp（thường dùng trong Quy hoạch động trạng thái）．
Bài toán yêu cầu thao tác bit．

Cần lưu ý, thay phép toán khác bằng thao tác bit nhiều khi không mang lại tối ưu rõ rệt, ngược lại làm code phức tạp hơn; cần cân nhắc khi dùng．

Ứng dụng liên quan lũy thừa của 2

Do thao tác bit dựa trên biểu diễn nhị phân, có nhiều ứng dụng liên quan đến lũy thừa nguyên của 2．

Nhân (chia) một số với lũy thừa nguyên không âm của 2：

C++Python

int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
  return n << m;
}

int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
  return n >> m;
}

def mulPowerOfTwo(n, m):  # 计算 n*(2^m)
    return n << m


def divPowerOfTwo(n, m):  # 计算 n/(2^m)
    return n >> m

Warning

Phép chia thường dùng là làm tròn về \(0\), còn dịch phải là làm tròn xuống (lưu ý khác biệt này): khi số \(\ge 0\) thì hai cách tương đương, khi số < 0 thì khác, ví dụ: -1 / 2 có giá trị \(0\) nhưng -1 >> 1 có giá trị \(-1\)．

Lấy trị tuyệt đối

Trên một số máy, nhanh hơn n > 0 ? n : -n．

C++Python

int Abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
  /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
    若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
    需要计算 n 和 -1 的补码，然后进行异或运算，
    结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */
}

def Abs(n):
    return (n ^ (n >> 31)) - (n >> 31)
    """
    n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
    若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
    需要计算 n 和 -1 的补码，然后进行异或运算，
    结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值
    """

Lấy max/min của hai số

Trên một số máy, nhanh hơn a > b ? a : b．

C++Python

// 如果 a >= b, (a - b) >> 31 为 0，否则为 -1
int max(int a, int b) { return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31)); }

int min(int a, int b) { return (a & ((a - b) >> 31)) | (b & (~(a - b) >> 31)); }

# 如果 a >= b, (a - b) >> 31 为 0，否则为 -1
def max(a, b):
    return b & ((a - b) >> 31) | a & (~(a - b) >> 31)


def min(a, b):
    return a & ((a - b) >> 31) | b & (~(a - b) >> 31)

Kiểm tra hai số khác 0 có cùng dấu hay không

C++Python

bool isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >= 0;
}

# 有 0 的情况例外
def isSameSign(x, y):
    return (x ^ y) >= 0

Hoán đổi hai số

Phương pháp này có hạn chế

Cách này chỉ dùng để hoán đổi hai số nguyên, phạm vi sử dụng hạn chế．

Với hoán đổi thông thường, khuyến nghị dùng std::swap trong algorithm．

void swap(int& a, int& b) { a ^= b ^= a ^= b; }

Thao tác trên bit nhị phân của một số

Lấy một bit của một số:

C++Python

// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) { return (a >> b) & 1; }

# 获取 a 的第 b 位，最低位编号为 0
def getBit(a, b):
    return (a >> b) & 1

Đặt một bit về \(0\):

C++Python

// 将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) { return a & ~(1 << b); }

# 将 a 的第 b 位设置为 0 ，最低位编号为 0
def unsetBit(a, b):
    return a & ~(1 << b)

Đặt một bit về \(1\):

C++Python

// 将 a 的第 b 位设置为 1 ，最低位编号为 0
int setBit(int a, int b) { return a | (1 << b); }

# 将 a 的第 b 位设置为 1 ，最低位编号为 0
def setBit(a, b):
    return a | (1 << b)

Đảo một bit:

C++Python

// 将 a 的第 b 位取反 ，最低位编号为 0
int flapBit(int a, int b) { return a ^ (1 << b); }

# 将 a 的第 b 位取反 ，最低位编号为 0
def flapBit(a, b):
    return a ^ (1 << b)

Các thao tác này tương đương coi biến int 32-bit như một mảng boolean độ dài 32．

Trọng số Hamming

Trọng số Hamming là số lượng ký hiệu khác ký hiệu zero trong một chuỗi ký hiệu (trên bộ ký tự dùng)．Với số nhị phân, trọng số Hamming bằng số lượng bit 1 (tức popcount)．

Cách tính trọng số Hamming bằng vòng lặp: liên tục bỏ bit thấp nhất (dịch phải 1 bit), duy trì biến đáp án, mỗi lần cập nhật tùy theo bit thấp nhất có là 1 hay không．

Code như sau:

// 求 x 的汉明权重
int popcount(int x) {
  int cnt = 0;
  while (x) {
    cnt += x & 1;
    x >>= 1;
  }
  return cnt;
}

Có thể dùng thao tác lowbit: liên tục trừ đi lowbit¹ cho tới khi số bằng 0．

Code như sau:

// 求 x 的汉明权重
int popcount(int x) {
  int cnt = 0;
  while (x) {
    cnt++;
    x -= x & -x;
  }
  return cnt;
}

Xây dựng hoán vị tăng theo trọng số Hamming

Trong Quy hoạch động trạng thái, đôi khi duyệt theo thứ tự popcount tăng để tránh duyệt trạng thái lặp．Đây là một ứng dụng quan trọng của việc xây dựng hoán vị tăng theo trọng số Hamming．

Dưới đây ta khảo sát cách xây dựng hoán vị tăng theo trọng số Hamming trong \(O(n)\)．

Ta biết, số nhỏ nhất có trọng số Hamming bằng \(n\) là \(2^n-1\)．Nếu có thể trong \(O(1)\) tìm “kế tiếp” có cùng trọng số Hamming, ta có thể duyệt theo trọng số từ \(2^n-1\) để xây dựng hoán vị của \(0\sim n\) trong \(O(n)\)．

Cách tìm phần tử kế tiếp có cùng trọng số Hamming với \(x\) có thể hiểu như sau, lấy \((10110)_2\) làm ví dụ:

Dịch bit 1 ở phải nhất sang trái, nếu không dịch được thì thử bit 1 bên trái, tiếp tục như vậy, được \((11010)_2\)．
Đưa tất cả bit 1 từ vị trí vừa dịch đến bit thấp nhất về phía phải nhất．Với ví dụ, bit 1 vừa dịch ở vị trí thứ 3, nên ba bit cuối 010 trở thành 001, được \((11001)_2\)．

Quá trình này có thể tối ưu bằng thao tác bit:

  int t = x + (x & -x);
  x = t | ((((t & -t) / (x & -x)) >> 1) - 1);

Bước đầu, ta cộng \(x\) với lowbit của nó, trong nhị phân tương đương thay đoạn liên tiếp 1 bên phải bằng một 1 bên trái của nó．Ví dụ \((10110)_2\) cộng lowbit thành \((11000)_2\)．Đây là nửa trước của đáp án．
Ta cần bổ sung các bit 1 ở cuối: lowbit(t) là vị trí sau khi bit 1 cao nhất trong đoạn liên tiếp dịch sang trái; lowbit(x) là vị trí thấp nhất của đoạn liên tiếp đó．Ví dụ \(t=(11000)_2\)，\(\operatorname{lowbit}(t)=(01000)_2\)，\(\operatorname{lowbit}(x)=(00010)_2\)．
Phép chia tiếp theo là phần khó nhất nhưng quan trọng: giả sử đoạn 1 liên tiếp của số gốc có bit cao nhất ở vị trí \(r\) (đánh số từ 0), bit thấp nhất ở vị trí \(l\)；lowbit(t)=1<<(r+1)，lowbit(x)=1<<l，khi đó (((t&-t)/(x&-x))>>1) = (1<<(r+1))/(1<<l)/2 = 1<<(r-l)，trong nhị phân là 1 kèm \(r-l\) số 0, đúng bằng số lượng 1 liên tiếp trừ 1．Ví dụ: \(\frac{\operatorname{lowbit(t)/2}}{\operatorname{lowbit(x)}} = \frac{(00100)_2}{(00010)_2} = (00010)_2\)．Trừ 1 sẽ ra phần cần bổ sung, OR với nửa trước sẽ ra đáp án．

Vì vậy, code đầy đủ để liệt kê \(0\sim n\) theo trọng số Hamming tăng là:

  for (int i = 0; (1 << i) - 1 <= n; i++) {
    for (int x = (1 << i) - 1, t; x <= n; t = x + (x & -x),
             x = x ? (t | ((((t & -t) / (x & -x)) >> 1) - 1)) : (n + 1)) {
      // 写下需要完成的操作
    }
  }

Lưu ý cần xử lý riêng trường hợp \(0\) vì \(0\) không có phần tử kế tiếp cùng trọng số Hamming．

Lớp và hàm liên quan trong C++

Hàm dựng sẵn của GCC

GCC có một số hàm dựng sẵn cho thao tác bit:

int __builtin_ffs(int x)：trả về vị trí bit 1 thấp nhất (tính từ 1), nếu \(x=0\) trả 0．
int __builtin_clz(unsigned int x)：số lượng 0 ở đầu (leading zeros), nếu \(x=0\) thì không xác định．
int __builtin_ctz(unsigned int x)：số lượng 0 liên tiếp ở cuối, nếu \(x=0\) thì không xác định．
int __builtin_clrsb(int x)：nếu bit dấu là 0, trả số lượng 0 đầu trừ 1; ngược lại trả số lượng 1 đầu trừ 1．
int __builtin_popcount(unsigned int x)：số lượng bit 1．
int __builtin_parity(unsigned int x)：tính chẵn lẻ của số bit 1．

Có thể thêm l hoặc ll để đổi kiểu tham số thành (unsigned)long hoặc (unsigned)long long (giá trị trả về vẫn là int)． Ví dụ, muốn lấy \(\log_2\) của một số (không xét \(0\)), tương đương số bit của biểu diễn nhị phân trừ 1．Với số nguyên N bit, số bit của n là N - __builtin_clz(n)，nên N - 1 - __builtin_clz(n) là \(\log_2 n\)．

Các hàm này là built-in nên được tối ưu rất tốt, tốc độ rất nhanh (thậm chí chỉ một lệnh)．

Nhiều bit hơn

Nếu cần thao tác dãy bit rất dài, có thể dùng std::bitset．

Đề bài gợi ý

Luogu P1225 黑白棋游戏

Tài liệu tham khảo và chú thích

lowbit của một số là bit 1 thấp nhất kèm theo các 0 phía sau, ví dụ \((1010)_2\) có lowbit là \((0010)_2\)，xem chi tiết ở Fenwick Tree． ↩

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply