Nó xảy ra rằng cần phải liệt kê tất cả các chuỗi bit có độ dài nhất định. Hay nói cách khác, lặp lại tất cả các tùy chọn có thể, trong đó đối với mỗi đối tượng, một trong hai trạng thái có thể được chọn.
Trong những tình huống như vậy, có thể thực hiện liệt kê bằng cách sử dụng mặt nạ bit. Ưu điểm của phương pháp này là mã như vậy hoạt động không đệ quy và hoạt động trên các số thay vì tập hợp hoặc tương tự, giúp cải thiện đáng kể hiệu suất.
Mã chung sử dụng bitmasks được đưa ra dưới đây:
intn; // số đối tượng (độ dài chuỗi bit)
for (int mask = 0; mask < (1 << n); mask++) { // lặp qua tất cả các số từ 0 đến 2^n - 1, trong đó mỗi số tương ứng với một bitmask
// mặt nạ số hiện tại là một bitmask, trong đó bit thứ i chỉ định trạng thái của đối tượng thứ i
for (int i = 0; i < n; i++) { // lặp lại n bit để biết trạng thái của từng đối tượng
if ((1 << i) & mask) { // kiểm tra xem bit thứ i có bằng 1 không
// xử lý tùy chọn mà đối tượng thứ i có trạng thái '1'
}
else { // trường hợp bit thứ i bằng 0
// xử lý tùy chọn đối tượng thứ i của trạng thái '0'
}
}
}
Mã này chạy trong O(2^n * f(n)), trong đó f(n) là thời gian bạn cần để xử lý một lần lặp cụ thể.
|
Nó xảy ra rằng cần phải liệt kê tất cả các chuỗi bit có độ dài nhất định. Hay nói cách khác, lặp lại tất cả các tùy chọn có thể, trong đó đối với mỗi đối tượng, một trong hai trạng thái có thể được chọn.
Trong những tình huống như vậy, có thể thực hiện liệt kê bằng cách sử dụng mặt nạ bit. Ưu điểm của phương pháp này là mã như vậy hoạt động không đệ quy và hoạt động trên các số thay vì tập hợp hoặc tương tự, giúp cải thiện đáng kể hiệu suất.
Mã chung sử dụng bitmasks được đưa ra dưới đây:
intn; // số đối tượng (độ dài chuỗi bit)
for (int mask = 0; mask < (1 << n); mask++) { // lặp qua tất cả các số từ 0 đến 2^n - 1, trong đó mỗi số tương ứng với một bitmask
// mặt nạ số hiện tại là một bitmask, trong đó bit thứ i chỉ định trạng thái của đối tượng thứ i
for (int i = 0; i < n; i++) { // lặp lại n bit để biết trạng thái của từng đối tượng
if ((1 << i) & mask) { // kiểm tra xem bit thứ i có bằng 1 không
// xử lý tùy chọn mà đối tượng thứ i có trạng thái '1'
}
else { // trường hợp bit thứ i bằng 0
// xử lý tùy chọn đối tượng thứ i của trạng thái '0'
}
}
}
Mã này chạy trong O(2^n * f(n)), trong đó f(n) là thời gian bạn cần để xử lý một lần lặp cụ thể.
|