位运算

2014/04/06

Categories: Algorithm Tags: bitwise c

大小写互相转换

如果仔细观察 ASCII 码表的话，就可以发现大小写字母的二进制表示中第 5 位相差一个 1 。于是大小写转换可以写成如下：

void ch(char *c) {
    *c = (*c) ^ (1<<5);
}

计算二进制 x 中 1 的个数

int one_count(unsigned int x) {
    x = (x&0x55555555UL) + ((x>>1)&0x55555555UL);
    x = (x&0x33333333UL) + ((x>>2)&0x33333333UL);
    x = (x&0x0f0f0f0fUL) + ((x>>4)&0x0f0f0f0fUL);
    x = (x&0x00ff00ffUL) + ((x>>8)&0x00ff00ffUL);
    x = (x&0x0000ffffUL) + ((x>>16)&0x0000ffffUL);

    return x;
}

二进制 data 右侧开始第一个 1 的位置

int bs(int data) {
    int pos = 0;

    if ((data & 0xFFFF) == 0) {
        data >>= 16;
        pos += 16;
    }

    if ((data & 0xFF) == 0) {
        data >>= 8;
        pos +=8;
    }

    if ((data & 0xF) == 0) {
        data >>= 4;
        pos += 4;
    }

    if ((data & 0x3) == 0) {
        data >>= 2;
        pos += 2;
    }

    if ((data & 0x1) == 0)
        pos += 1;

    return pos;
}

奇偶性判断

x&1

0 表示偶数，1 表示奇数

二进制状态压缩

常用于 \(n \le 15 \)的物品、位置等的状态枚举


// i 的二进制表示一个状态，为 0 的位置表示不存在，1 表示存在
for(int i = 0;i < 1<<(n-1);i ++) {    
    for(int j = 1;j <= n;j ++)
        if(i & (1<<(j-1))) { //如果第 j 个位置为 1
            // Todo
        }
}