C语言中的位运算

复习一下C语言中的位运算。

1. 使用位运算求相反数

/**
 * For each integer x, return -x.
 * eg. 5 => -5,  -6 => 6, 0 => 0
 */
int negate(int x) {
    return ~x + 1;
}

2. 判断两个整数是否相等

/**
 * return 1 if x == y, and 0 otherwise
 * eg. f(5,5) = 1,  f(5, 6) = 0, f(-1, -1) = 1
 */
int isEqual(int x, int y) {
    return ! (x ^ y);
}

3. 将整数的二进制表示全部设置成最低位的数字

/**
 * Set all bits of result to least significant bit of x
 */
int copyLeastSignificantBit(int x) {
    return ~(x & 1) + 1;
}

4. 求最大的二进制补码

/**
 * return maximumn two's complement integer
 */
int maxTwoComplementValue(void) {
    return ~(1<<31);
}

5. 二进制中1的个数

// 统计二进制中1的个数
int count1InBit(int num) {
    int count = 0;
    while (num) {
        count++;
        num &= (num - 1);
    }
    return count;
}

6. 获取非0整数的二进制最低的一个1

// 二进制中最低位的1
// eg. xxx1000 => 0001000
int findLeastSignificant1(int num) {
    // or: num ^ (num & (num - 1))
    // or: num & -num
    return num & (~num + 1);
}

7. 统计数组中只出现一次的数字-I

#include <stdio.h>

/* 统计int数组中只出现一次的数字。数组中除了1个数不同外，其他都是成对出现
 * eg. data = [1,2,3,1,2] => 3
 * 利用了异或的性质:  x ^ x = 0, 0 ^ x = x
*/
int appearOnce(int data[], int n) {
    int ans = 0, i = 0;
    for (; i < n; i++) {
        ans ^= data[i];
    }
    return ans;
}

int main() {
    int data[] = {1,2,3,1,2};
    int num = appearOnce(data, 5);
    printf("%d \n", num);
}

8. 统计数组中只出现一次的数字-II

#include <stdio.h>

/* 统计int数组中只出现一次的数字。数组中除了2个数不同外，其他都是成对出现
 * eg. data = [1,2,3,1,2,5] => 3,5
 * 利用了异或的性质:  x ^ x = 0, 0 ^ x = x
 * 思路：将输入的data分成两组，使得每组只包含一个不同的数字，转化成上面一个问题
 * 难点：如何划分成两组且使得两个不同的数字分别包含在其中？根据异或的性质，两个不同的数字异或后一定不为0，按照二进制某一位为1来划分即可
*/
void findAppearOnce(int data[], int n) {
    int ans = 0, i = 0;
    for (; i < n; i++) {
        ans ^= data[i];
    }
    int x = 0, y = 0;
    if (ans == 0) {
        printf("Illegal input!");
        return;
    }

    int mask = ans ^ (ans & (ans - 1)); // 获取ans中最低一位为1的掩码 (0...010...0)
    // 获取mask的方式不止一种：  mask = ans ^ (~ans + 1)
    for (i = 0; i < n; i++) {
        if ((mask & data[i]) == mask) {
            x ^= data[i];
        } else {
            y ^= data[i];
        }
    }
    printf("Found two distinct numbers: %d, %d\n", x, y);
}

int main() {
    int data[] = {1,2,3,1,2,5,7,7,8,8,9,9};
    findAppearOnce(data, sizeof(data)/sizeof(int));
}

9. 将byte数据按位逆置

/**
 * input: A single char value.
 * return: A char which has a binary representation which is the input char's binary in reverse order.
 */
char bitReverse(char ch) {
    char ans = 0;
    for (int i = 0; i < 8; i++) {
        ans = (ans << 1) + (ch & 1);
        ch >>= 1;
    }
    return ans;
}

10. 不用加减乘除做加法

可以先观察一位二进制数的加法，不考虑进位。然后考虑2位二进制，同时考虑进位。

int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a ^= b;
        b = carry;
    }
    return a;
}

11. 使用位运算实现函数f(x) = 3x/4

分析：这里的3x，可以拆成2x + x; 除以4，直接采用右移2位来做。

int multiDivideWithBit(int x) {
    int val = (x << 1); // 计算2x

    // 计算2x + x = 3x (利用了前一节的位运算做加法）
    int sum = val, y = x;
    while (y != 0) {
        int carry = (sum & y) << 1;
        sum ^= y;
        y = carry;
    }

    return sum >> 2; // 实现除4的效果
}