位运算的实用技巧

大小写字母转化

对比大小写字母的 ASCII 码如下

$\begin{array}{ccccccc} \text{alpha} & A/a & B/b & C/c & \cdots & Y/y & Z/z\\ \text{upper} & 01\textcolor{red}{0}00001 & 01\textcolor{red}{0}00010 & 01\textcolor{red}{0}00011 & \cdots & 01\textcolor{red}{0}11001 & 01\textcolor{red}{0}11010\\ \text{lower} & 01\textcolor{red}{1}00001 & 01\textcolor{red}{1}00010 & 01\textcolor{red}{1}00011 & \cdots & 01\textcolor{red}{1}11001 & 01\textcolor{red}{1}11010\\ \end{array}$

可以发现大小写字母只在第六位有差别，因此只要改变第六位，就能实现大小写的转化

大写/小写转小写

要将大写字母/小写字母转化为小写字母，就是将第六位变为 1，考虑掩码 0010 0000，任何一个数与其进行与运算，除第六位变成 1 外，其他位保持不变，因此就可以得到

char to_lower(char ch)
{
    return ch | 32;
}

也可以用 32 对应的 ASCII 值即 ' '，因此可以得到

char to_lower(char ch)
{
    return ch | ' ';
}

大写/小写转大写

要将大写字母/小写字母转为大写字母，只需要保证第六位为 0，考虑掩码 1101 1111，即 233（_ 的 ASCII 码）就可以实现这个操作

char to_upper(char ch)
{
    return ch & '_';
}

大小写互相转化

还是考虑 0010 0000，但是这里用异或运算

char toggle(char ch)
{
    return ch ^ ' ';
}

实际上，在 C23 标准中，C 语言已经支持了二进制的变量写法，如 0b00100000，因此可以不用记忆相应的字符或是进行进制转化

至于较老的标准，可以使用十六进制，比如 0010 0000 对应的十六进制数为 0x20，1101 1111 对应的十六进制数为 0xDF，那么也就可以得到下面几个函数

char to_lower(char ch)
{
    return ch | 0x20;
}

char to_upper(char ch)
{
    return ch & 0xDF;
}

char toggle(char ch)
{
    return ch ^ 0x20;
}

n&(n-1) ^[1]

我们不妨设 $n = 1001 0110$ 来探究这个算式的含义

$\begin{array}{} & 1001 0110 & \text{n}\\ \text{and} & 1001 0101 & \text{n - 1}\\ \hline & 1001 0100 & \text{n \& (n - 1)} \end{array}$

初看猜想这个算式会消除最后一个 1，这个猜想不难验证

如果最低位是 1，那么显然这个 1 在运算后会被消除

如果最低位是 0（或有连续多个 0），那么在减去 1 后，这些 0 都会变成 1，而最低位的 1 会变成 0，那么经过这个运算后，结果就是最低位的 1 被消除

计算汉明权重（Hammming Weight）

汉明权重：一个无符号整数的二进制表达中的 1 的位数

通过循环消除 1 来计数即可实现计算汉明权重

int hamming_weight(int n)
{
    int res = 0;
    while (n != 0)
    {
        n = n & (n - 1); // 消除最末的 1
        res++; // 计数器累加
    }
    return res;
}

判断一个数是不是 2 的指数

2 的指数满足其二进制表达只有一个 1，因此可以如下判断

bool is_power_two(int n)
{ 
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

判断奇偶数

根据二进制的计数规律，奇数的最低位是 1，偶数的最低位是 0，因此可以用类似下面的代码判断奇偶数

int n;
scanf("%d", &n);
if (n & 1) // n & 1 == 1
    printf("Odd\n");
else
    printf("Even\n");

交换两个数

利用异或运算的两个性质 a ^ a = 0，a ^ 0 = a，则可实现两数交换

1
2
3

a = a ^ b;
b = a ^ b; // (a ^ b) ^ b = a
a = a ^ b; // (a ^ b) ^ a = b

删除成对的数字

给定一个数组，其中只有一个数是不成对的，要找出这个数

可以用异或运算，利用其性质：a ^ a = 0，a ^ 0 = a 即可，如下

int solu(int nums[], int len)
{
    int res = 0;
    for (int i = 0; i < len; i++)
        res ^= nums[i];
    return res;
}

这里还可以看看洛谷 P1469 找筷子

位向量的基本操作

对于一个八位二进制数，有如下基本操作

操作名称	逻辑公式	C 语言实现
置位（Set）	`V \| (1 << i)`	`v \|= 1 << i`
复位（Clear）	`V & ~(1 << i)`	`v &= ~(1 << i)`
翻转（Flip）	`V ^ (1 << i)`	`v ^= 1 << i`
测试1（Test）	`V & (1 << i)`	`if (v & (1 << i))`
测试2（Test）	`(V >> i) & 1`	`if ((v >> i) & 1)`

这里去可以尝试洛谷 P1100 高低位交换

利用其中一些操作可以模拟bis和bic的底层逻辑如下

#include <stdint.h>

typedef uint8_t byte;

byte bis(byte x, byte m)
{
    for (int i = 0; i < 8; i++)
    {
        // 提取 m 的第 i 位
        byte mask_bit = (m >> i) & 1;
        // 将该位“搬运”到 x 的对应位置
        // 如果 mask_bit 是 0，或运算不改变结果
        // 如果 mask_bit 是 1，对应的位被置 1
        x |= (mask_bit << i);
    }
    return x;
}

byte bic(byte x, byte m)
{
    byte result = x;
    for (int i = 0; i < 8; i++)
    {
        // 提取掩码 m 的第 i 位
        int mask_bit = (m >> i) & 1;

        // 如果掩码位是 1，说明我们要“清除”这一位
        if (mask_bit == 1)
        {
            // 构造一个在该位为 0，其余位全为 1 的“清除器”
            byte killer = ~((byte)1 << i);
            result &= killer;
        }
    }
    return result;
}