详解位运算

详解C语言中的位运算。

基本应用

判断奇偶

思路：

任何整数，如果是奇数，则转化为二进制数后，最后一位二进制位肯定为1，为偶数，则最后一位二进制位为0。利用这个性质，将任意整数x与1作与运算，如果结果为1，则x为奇数；结果为0，则x为0数。

int is_odd(int x) {//偶数
    return x & 1;
}

int is_even(int x) {//奇数
    return!(x & 1);
}

交换两个数

思路：

两个数a和b，可以用异或运算来交换它们的值。a^b的结果是a和b的不同位的组合，而a^b^a的结果是a和b的相同位的组合。利用这个性质，可以将a和b的值交换。

void swap(int *a, int *b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

结果：

交换前：a=3 b=6
交换后：a=6 b=3

取绝对值

思路：

任何整数的绝对值，可以用位运算来实现。如果整数x是正数，则x的绝对值等于x；如果整数x是负数，则x的绝对值等于其二进制表示的补码。利用这个性质，可以将任意整数x的绝对值取出来。

这个方法和类型紧密相关

int abs(int x) {
    int mask = x >> 31; // 右移31位，得到最右边的1
    return (x + mask) ^ mask; // 利用异或运算求绝对值
}

取最小值

思路：

两个整数的最小值，可以用位运算来实现。如果a和b都是正数，则它们的最小值等于a和b的按位与结果；如果a和b有一个为负数，则它们的最小值等于负数的绝对值与另一个数的按位与结果。利用这个性质，可以将任意两个整数的最小值取出来。

这个方法和类型紧密相关

int min(int a, int b) {
    int mask = (a - b) >> 31; // 右移31位，得到最右边的1
    return (a & ~mask) | (b & mask); // 利用按位与和按位或运算求最小值
}

操作位

#define BitVal(data,y) ( (data>>y) & 1)             // Return Data.Y value
#define SetBit(data,y)    data |= (1 << y)          // Set Data.Y to 1
#define ClearBit(data,y)  data &= ~(1 << y)         // Clear Data.Y to 0
#define TogleBit(data,y)     (data ^=BitVal(y))     // Togle Data.Y value
#define Togle(data)   (data =~data )                // Togle Data value

参考资料

• 位运算