数据结构 位运算

基础位运算

按位与（AND）

• 操作符：&
• 两个位同时位1时，结果位1，否则为0

按位或（OR）

• 操作符：|
• 主要有一位是1，那么结果就是1，只有两位都是0的时候，结果才是0

按位异或（XOR）

• 操作符：^
• 当两个位不同的时候（一位是0，另一位是1）的时候，结果为1，否则都为0 

按位取返（NOT）

• 操作符：~
• 将每个位都取反，0变1,1 变0

左移

• 操作符：<<
• 所有位向左移动指定位数，然后右边补0 

右移

• 操作符：>>
• 将所有位向右移动指定的位数，对于无符号树左边补0，对于有符号的数则补充符号位的值（正数补0，负数补1） 

常用位计算

给一个数n，确定它的二进制表示中的第x位是0还是1

• 掩码生成：1 << (x - 1) 将 1 左移 x-1 位，生成一个只有第 x 位为 1 的掩码。例如，当 x = 3 时，生成的掩码为 0100
• 按位与操作：n & mask 会保留 n 中第 x 位的值，并将其它位设为 0。如果结果不等于 0，说明第 x 位为 1

#include <iostream>

bool checkBit(int n, int x) {
    // 生成掩码，1 左移 (x-1) 位
    int mask = 1 << (x - 1);
    // 按位与操作，检查第 x 位
    return (n & mask) != 0;
}

int main() {
    int n = 13;  // 二进制表示为 1101
    int x = 3;

    if (checkBit(n, x)) {
        std::cout << "第 " << x << " 位是 1" << std::endl;
    } else {
        std::cout << "第 " << x << " 位是 0" << std::endl;
    }

    return 0;
}

将一个数n的二进制表示的第x位修改成1

• 生成一个只有第 x 位为 1 的掩码：将 1 左移 (x-1) 位。
• 将 N 与这个掩码进行按位或操作：这样可以确保 N 的第 x 位被设置为 1，而不影响其他位的值

#include <iostream>

int setBitToOne(int N, int x) {
    // 生成掩码，1 左移 (x-1) 位
    int mask = 1 << (x - 1);
    // 按位或操作，设置第 x 位为 1
    return N | mask;
}

int main() {
    int N = 13;  // 二进制表示为 1101
    int x = 2;

    int result = setBitToOne(N, x);

    std::cout << "修改后的结果是: " << result << std::endl;  // 输出修改后的数值
    //std::cout << "二进制表示: " << std::bitset<8>(result) << std::endl;  // 输出二进制表示

    return 0;
}

将一个数n的二进制表示的第x位修改成0

• 生成一个只有第 x 位为 1 的掩码：将 1 左移 (x-1) 位。
• 对掩码取反：将掩码的第 x 位变成 0，其他位变成 1。
• 将 N 与取反后的掩码进行按位与操作：这样可以将 N 的第 x 位设置为 0，而不影响其他位的值

#include <iostream>

int clearBitToZero(int N, int x) {
    // 生成掩码，1 左移 (x-1) 位
    int mask = 1 << (x - 1);
    // 对掩码取反，然后与 N 进行按位与操作
    return N & ~mask;
}

int main() {
    int N = 13;  // 二进制表示为 1101
    int x = 3;

    int result = clearBitToZero(N, x);

    std::cout << "修改后的结果是: " << result << std::endl;  // 输出修改后的数值

    return 0;
}

提取一个数n二进制表示中最右侧的1

• -n 是 n 的二进制补码表示，实际上等于 ~n + 1。
• n & -n 的结果保留了 n 中最右侧的 1，其余位都被置为 0

#include <iostream>

int extractRightmostOne(int n) {
    return n & -n;
}

int main() {
    int n = 18;  // 二进制表示为 10010

    int result = extractRightmostOne(n);
    
    std::cout << "最右侧的1: " << result << std::endl;  // 输出结果
    std::cout << "二进制表示: " << std::bitset<8>(result) << std::endl;  // 输出二进制表示

    return 0;
}

删除一个数n二进制表示中最右侧位的1

• 当 n 减去 1 时，n 最右侧的 1 以及它右边的所有位都会被翻转。
• 将 n 与 n-1 进行按位与操作，会清除掉 n 最右侧的 1，并保持其他位不变

#include <iostream>

int clearRightmostOne(int n) {
    return n & (n - 1);
}

int main() {
    int n = 18;  // 二进制表示为 10010

    int result = clearRightmostOne(n);

    std::cout << "清除最右侧的1后的结果: " << result << std::endl;  // 输出结果

    return 0;
}