Phép toán bit (Bitwise): 6 mẹo thao tác bit kinh điển, code C++ và Python

#include <iostream>
using namespace std;

// 1. Kiểm tra bit thứ k của x (trả về 1 hoặc 0)
int kiemTraBit(long long x, int k) {
    return (x >> k) & 1LL;
}

// 2. Bật bit thứ k của x lên 1
long long batBit(long long x, int k) {
    return x | (1LL << k);
}

// 3. Tắt bit thứ k của x về 0
long long tatBit(long long x, int k) {
    return x & ~(1LL << k);
}

// 4. Đảo trạng thái bit thứ k của x (0 thành 1, 1 thành 0)
long long daoBit(long long x, int k) {
    return x ^ (1LL << k);
}

// 5. Kiểm tra x có phải lũy thừa của 2 không (2^0, 2^1, 2^2, ...)
bool laLuyThuaCua2(long long x) {
    return x > 0 && (x & (x - 1)) == 0;
}

// 6. Đếm số lượng bit 1 của x theo thuật toán Brian Kernighan
int demBit1(long long x) {
    int dem = 0;
    while (x > 0) {
        x &= (x - 1);  // xóa bit 1 thấp nhất ở mỗi bước
        dem++;
    }
    return dem;
}

// 7. Lấy giá trị của bit 1 thấp nhất (2^k nhỏ nhất chia hết x)
long long bit1ThapNhat(long long x) {
    return x & (-x);
}

int main() {
    long long x = 13;  // 13 ở hệ nhị phân là 1101 (bit 0, 2, 3 bằng 1; bit 1 bằng 0)
    cout << kiemTraBit(x, 2) << " " << kiemTraBit(x, 1) << "\n";  // 1 0
    cout << batBit(x, 1) << "\n";                                 // 15 (1111)
    cout << tatBit(x, 2) << "\n";                                 // 9  (1001)
    cout << daoBit(x, 0) << "\n";                                 // 12 (1100)
    cout << laLuyThuaCua2(16) << " " << laLuyThuaCua2(18) << "\n"; // 1 0
    cout << demBit1(x) << "\n";                                   // 3
    cout << bit1ThapNhat(12) << "\n";                             // 4  (1100 -> 0100)
    return 0;
}

def kiem_tra_bit(x, k):
    """Kiểm tra bit thứ k của x (trả về 1 hoặc 0)."""
    return (x >> k) & 1


def bat_bit(x, k):
    """Bật bit thứ k của x lên 1."""
    return x | (1 << k)


def tat_bit(x, k):
    """Tắt bit thứ k của x về 0."""
    return x & ~(1 << k)


def dao_bit(x, k):
    """Đảo trạng thái bit thứ k của x (0 thành 1, 1 thành 0)."""
    return x ^ (1 << k)


def la_luy_thua_cua_2(x):
    """Kiểm tra x có phải lũy thừa của 2 không (trả về 1 hoặc 0)."""
    return 1 if (x > 0 and (x & (x - 1)) == 0) else 0


def dem_bit_1(x):
    """Đếm số lượng bit 1 của x nguyên không âm bằng mẹo xóa bit 1 thấp nhất."""
    dem = 0
    while x > 0:
        x &= x - 1
        dem += 1
    return dem


def bit_1_thap_nhat(x):
    """Lấy giá trị của bit 1 thấp nhất."""
    return x & (-x)


x = 13  # 13 ở hệ nhị phân là 1101
print(kiem_tra_bit(x, 2), kiem_tra_bit(x, 1))       # 1 0
print(bat_bit(x, 1))                                # 15
print(tat_bit(x, 2))                                # 9
print(dao_bit(x, 0))                                # 12
print(la_luy_thua_cua_2(16), la_luy_thua_cua_2(18)) # 1 0
print(dem_bit_1(x))                                 # 3
print(bit_1_thap_nhat(12))                          # 4

#include <iostream>
#include <vector>
using namespace std;

// Đếm số tập con của mảng a có tổng đúng bằng S bằng kỹ thuật Bitmask
int demTapConCoTong(const vector<int>& a, long long S) {
    int n = (int)a.size();
    int soTapCon = 0;

    // Duyệt mọi trạng thái mask từ 0 đến 2^n - 1
    for (int mask = 0; mask < (1 << n); mask++) {
        long long tong = 0;
        for (int i = 0; i < n; i++) {
            // Nếu bit thứ i của mask bật (bằng 1) thì chọn phần tử a[i]
            if ((mask >> i) & 1) {
                tong += a[i];
            }
        }
        if (tong == S) {
            soTapCon++;
        }
    }
    return soTapCon;
}

int main() {
    cout << demTapConCoTong({3, 5, 7, 8, 10}, 15) << "\n";  // 3 ({5,10}, {7,8}, {3,5,7})
    cout << demTapConCoTong({2, 4, 6}, 5) << "\n";          // 0
    cout << demTapConCoTong({1, 2, 3, 4}, 6) << "\n";       // 2 ({2,4}, {1,2,3})
    return 0;
}

def dem_tap_con_co_tong(a, s):
    """Đếm số tập con của danh sách a có tổng đúng bằng s bằng kỹ thuật Bitmask."""
    n = len(a)
    so_tap_con = 0

    # Duyệt mọi trạng thái mask từ 0 đến 2^n - 1
    for mask in range(1 << n):
        tong = 0
        for i in range(n):
            if (mask >> i) & 1:
                tong += a[i]
        if tong == s:
            so_tap_con += 1
    return so_tap_con


print(dem_tap_con_co_tong([3, 5, 7, 8, 10], 15))  # 3
print(dem_tap_con_co_tong([2, 4, 6], 5))          # 0
print(dem_tap_con_co_tong([1, 2, 3, 4], 6))       # 2