C++位運(yùn)算技巧咋運(yùn)用

c++
小樊
81
2024-11-08 20:32:33
欄目: 編程語言

C++中的位運(yùn)算符允許你直接操作二進(jìn)制位，這可以提高程序的性能，減少內(nèi)存使用，并且有時(shí)可以使代碼更加簡(jiǎn)潔和高效。以下是一些常見的位運(yùn)算技巧及其在C++中的應(yīng)用：

  1. 按位與（&）：對(duì)應(yīng)位都為1時(shí)結(jié)果為1，否則為0。
  2. 按位或（|）：對(duì)應(yīng)位有一個(gè)為1時(shí)結(jié)果為1，否則為0。
  3. 按位異或（^）：對(duì)應(yīng)位不同時(shí)結(jié)果為1，相同時(shí)為0。
  4. 按位取反（~）：將每一位二進(jìn)制數(shù)值取反，即0變?yōu)?，1變?yōu)?。
  5. 左移（<<）：將位向左移動(dòng)指定的位數(shù)，右邊空出的位用0填充。
  6. 右移（>>）：將位向右移動(dòng)指定的位數(shù)，對(duì)于無符號(hào)數(shù)，左邊空出的位用0填充；對(duì)于有符號(hào)數(shù)，行為依賴于具體的實(shí)現(xiàn)，可能是填充0（邏輯右移），也可能是填充符號(hào)位（算術(shù)右移）。
  7. 位運(yùn)算符的組合使用：可以通過組合使用上述位運(yùn)算符來實(shí)現(xiàn)更復(fù)雜的功能，如檢查一個(gè)數(shù)的奇偶性（num & 1）、計(jì)算一個(gè)數(shù)的二進(jìn)制表示中1的個(gè)數(shù)（通過循環(huán)和位運(yùn)算實(shí)現(xiàn)）等。

以下是一些位運(yùn)算技巧的具體應(yīng)用示例：

1. 檢查奇偶性

int num = 15;
bool isEven = !(num & 1); // true, 因?yàn)?5的二進(jìn)制是1111，最后一位是1，所以是奇數(shù)

2. 計(jì)算二進(jìn)制表示中1的個(gè)數(shù)

int num = 15;
int count = 0;
while (num) {
    count += num & 1; // 如果最后一位是1，計(jì)數(shù)加1
    num >>= 1; // 右移一位
}

3. 快速冪算法

位運(yùn)算可以用于實(shí)現(xiàn)快速冪算法，從而高效地計(jì)算a^n % mod。

int fastPower(int base, int exponent, int mod) {
    long long result = 1;
    base = base % mod;
    while (exponent > 0) {
        if (exponent % 2 == 1) { // 如果當(dāng)前位是1
            result = (result * base) % mod;
        }
        exponent = exponent >> 1; // 右移一位
        base = (base * base) % mod; // 平方
    }
    return static_cast<int>(result);
}

4. 交換兩個(gè)變量的值

不需要使用臨時(shí)變量就可以交換兩個(gè)變量的值。

int a = 5, b = 7;
a = a ^ b; // a現(xiàn)在是12 (二進(jìn)制0110)
b = a ^ b; // b現(xiàn)在是5 (二進(jìn)制0101)
a = a ^ b; // a現(xiàn)在是7 (二進(jìn)制0111)

5. 使用位掩碼進(jìn)行權(quán)限控制

#define PERMISSION_READ 0b0001 // 二進(jìn)制0001
#define PERMISSION_WRITE 0b0010 // 二進(jìn)制0010
#define PERMISSION_EXECUTE 0b0100 // 二進(jìn)制0100

int main() {
    int permissions = PERMISSION_READ | PERMISSION_WRITE; // 二進(jìn)制0011
    if ((permissions & PERMISSION_READ) == PERMISSION_READ) {
        // 有讀權(quán)限
    }
    return 0;
}

6. 使用位運(yùn)算優(yōu)化數(shù)組排序

位運(yùn)算可以用于優(yōu)化某些特定類型的數(shù)組排序，例如整數(shù)數(shù)組。

void sortArray(int* arr, int size) {
    for (int i = 0; i < size - 1; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {
            if ((arr[j] & 0x55555555) > (arr[j + 1] & 0x55555555)) { // 使用0x55555555(二進(jìn)制10101010...)進(jìn)行比較
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

7. 使用位運(yùn)算優(yōu)化字符串處理

位運(yùn)算可以用于字符串的某些操作，例如檢查子串是否存在。

bool containsSubstring(const std::string& str, const std::string& substr) {
    if (substr.size() > str.size()) return false;
    for (size_t i = 0; i <= str.size() - substr.size(); ++i) {
        bool match = true;
        for (size_t j = 0; j < substr.size(); ++j) {
            if ((str[i + j] & ~substr[j]) != str[i + j]) { // 檢查字符是否匹配
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

8. 使用位運(yùn)算優(yōu)化內(nèi)存使用

位運(yùn)算可以用于優(yōu)化內(nèi)存使用，例如通過位字段來存儲(chǔ)多個(gè)布爾值。

struct Flags {
    unsigned int isEnabled : 1; // 二進(jìn)制0001
    unsigned int isActive : 1; // 二進(jìn)制0010
    // ...其他標(biāo)志位
};

9. 使用位運(yùn)算優(yōu)化循環(huán)

位運(yùn)算可以用于優(yōu)化循環(huán)，例如通過位掩碼來控制循環(huán)的執(zhí)行次數(shù)。

int countBits(int num) {
    int count = 0;
    while (num) {
        count += num & 1; // 如果最后一位是1，計(jì)數(shù)加1
        num >>= 1; // 右移一位
    }
    return count;
}

10. 使用位運(yùn)算優(yōu)化條件判斷

位運(yùn)算可以用于優(yōu)化條件判斷，例如通過位掩碼來檢查多個(gè)條件是否滿足。

int checkAccess(int permissions, int requiredPermissions) {
    return permissions & requiredPermissions; // 檢查是否有權(quán)限
}

通過合理使用這些位運(yùn)算技巧，你可以在C++中編寫出更加高效和簡(jiǎn)潔的程序。

0 踩