algo-aha

• x去掉最后一位1：x & (x-1)

• x只取最后一位1：x & -x

“范围与”的结果是首尾两数二进制的公共前缀

• https://leetcode.com/problems/bitwise-and-of-numbers-range/

int rangeBitwiseAnd(int m, int n) {
    // "范围与"的结果是：首尾两数二进制的公共前缀
    // 因为非公共前缀一定是0xxx和1xxx的形式，存在中间数1000将这部分"范围与"清零
    while (n > m) {
        n &= n - 1; // 去掉最后1位
    }
    return n;
}

4的幂

• https://leetcode.com/problems/power-of-four/

bool isPowerOfFour(int num) {
    // 二进制仅有一个1，且这个1出现在...010101这些位
    return num > 0 && (num & (num - 1)) == 0 && (num & 0x55555555) != 0;
}

数字有效位反转

• https://leetcode.com/problems/number-complement/

int findComplement(int num) {
    // 先找哪些是有效位
    int mask = ~0;
    while (mask & num) mask <<= 1;
    return ~mask ^ num;
}

位运算实现两数相加

• https://leetcode.com/problems/sum-of-two-integers/

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

也适用于负数，负数是补码表示。

字母变换大小写

• https://leetcode.com/problems/letter-case-permutation/

回溯法。根据ascii表，letter^=32就变换大小写，32 == 刚好>字母数26的 2的幂。

不用比较符找两数的较大值

不用比较符，表达式ans = cond ? a : b;等价于 ans = cond * a + !cond * b

≥号的表达式cond = (a>=b) = (a-b >= 0) = sign(a-b)。当a,b异号时a-b可能溢出，sign(a-b)不能用；而a,b异号，a>0>b或a<0<b，sign(a-b)==sign(a)，于是用sign(a)代替sign(a-b)。因此 cond = (a,b异号) ? sign(a) : sign(a-b)，较大的数 = cond * a + !cond * b。

见ctci p476