位运算技巧

有趣小技巧

大小写相互转换

xxxxxxxxxx
// 转小写
(char) ('a' | ' ') = 'a'
(char) ('A' | ' ') = 'a'

// 转大写
(char) ('b' & '_') = 'B'
(char) ('B' & '_') = 'B'

// 大小写互转
(char) ('d' ^ ' ') = 'D'
(char) ('D' ^ ' ') = 'd'

判断两个数是否异号

xxxxxxxxxx
int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true

int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false

不用临时变量交换两个数

xxxxxxxxxx
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1

加减一

xxxxxxxxxx
// 加一
int n = 1;
n = -~n;
// 现在 n = 2

// 减一
int n = 2;
n = ~-n;
// 现在 n = 1

算法常用操作

n & (n - 1)

可以消除 n 的二进制中最后一位 1

例题：

• 详情可见 191. 位1的个数
• 判断一个数是不是 2 的指数（如果一个数是 2 的指数，那么该数的二进制中只会有一个 1）

a ^ a = 0 a ^ 0 = a

详情可见 136. 只出现一次的数字

「任意位置」置 1 or 0

详情可见 698. 划分为k个相等的子集

xxxxxxxxxx
// 注意：「<<」优先级大于「|=」「^=」
// 将第 i 位标记为 1
used |= 1 << i;

// 将第 i 位标记为 0
used ^= 1 << i;

判断某一位置是否位 0

xxxxxxxxxx
((used >> i) & 1) == 1

低位的 0 变成 1

xxxxxxxxxx
n |= n + 1;

低位的 1 变成 0

xxxxxxxxxx
n &= n - 1;

实战题目

二叉树中的伪回文路径

题目详情可见 二叉树中的伪回文路径

这是一道综合运用位运算的高级题目 哈哈哈哈哈 我感觉很值得总结一波

首先这个题目肯定是需要用遍历的方法去写，遍历出所有路径

其次是需要搞清楚怎么判断是否为一个伪回文路径

• 出现次数为奇数的数字要么只有一个 要么没有

xxxxxxxxxx
// 记录每条路径
private int count = 0;
// 记录结果
private int res = 0;
public int pseudoPalindromicPaths (TreeNode root) {
    traversal(root);
    return res;
}
private void traversal(TreeNode root) {
    if (root == null) return ;
    // 对于每一个节点的表示：2:10 3:100 4:1000，以此类推
    // 刚好可以用左移来表示：1 << root.val
    // 当一个数出现两次后，则 10 ^ 10 = 0，利用了异或操作的特性，刚好可以抵消出现偶数次数的情况
    count ^= (1 << root.val);
    if (root.left == null && root.right == null) {
        if ((count & (count - 1)) == 0) res++;
    }
    traversal(root.left);
    traversal(root.right);
    // 再进行一次异或，刚好可以抵消上面异或操作
    // 正好是后序遍历离开节点时的操作
    count ^= (1 << root.val);
}

最小 XOR

题目详情可见 最小 XOR

xxxxxxxxxx
public int minimizeXor(int num1, int num2) {
    int c1 = Integer.bitCount(num1);
    int c2 = Integer.bitCount(num2);
    // num1 低位的 0 变成 1
    for (; c1 < c2; c1++) num1 |= num1 + 1;
    // num2 低位的 1 变成 0
    for (; c2 < c1; c2++) num1 &= num1 - 1;
    return num1;
}