位运算常用技巧

目录
前言
常用方法
基础运算符
高频位运算技巧
判断相同/不同字符的个数
拼接 + 判断一个数是否为2的幂

前言

力扣最近几天的每日一题基本都与位运算有关，让本就没有专门训练的鄙人在“模拟 -> 超时/报错”的循环中有些裂开。于是决定重学位运算，并将自己遇到的一些套路整合一下。

常用方法

bitCount(int n)

接收一个整数n，返回n的二进制中有多少个1

底层 Brian Kernighan 算法

int count = 0;
while (n != 0) {
    n = n & (n - 1);
    count++;

}

每执行一次 n & (n-1)，都会消掉最低位的一个 1。

基础运算符

与 &

两个位都为 1 才是 1
用途：

判断某一位是否为 1
判断是否为 2 的幂
清除最低位的 1
例：

1	n & 1 // 判断奇偶

或 |

有一个为 1 就是 1
用途：

置某一位为 1
拼接二进制

非 ~

按位取反

Java 是补码表示

1	~x = -x - 1

异或 ^

不同为 1，相同为 0

核心性质：
a ^ a = 0
a ^ 0 = a
满足交换律和结合律

用途：

找只出现一次的数
交换两个数
判断不同位

高频位运算技巧

1. 判断奇偶

1	(n & 1) == 0 // 偶数

2. 取最低位的 1

1	lowbit = n & (-n);

例：

1
2
3

n = 12 = 1100  
-n = 0100  
结果 = 0100

用途：

树状数组
快速拆分二进制

3. 删除最低位的 1

1	n = n & (n - 1);

4. 判断第 k 位是否为 1

1	((n >> k) & 1) == 1

5. 设置第 k 位为 1

1	n = n \| (1 << k);

6. 清除第 k 位

1	n = n & ~(1 << k);

7. 切换第 k 位

1	n = n ^ (1 << k);

判断相同/不同字符的个数

用一个整数作为 26 位 bitmask。

例如：

int mask = 0;
for (char c : s.toCharArray()) {
    mask ^= (1 << (c - 'a'));
}

用途：

判断是否出现奇数次
回文排列问题

拼接 + 判断一个数是否为2的幂

拼接

左移 + 或

1	result = (result << shift) \| x;

a << b将 a 的二进制表示向左移动 b 位，
相当于乘以 2^b，
在右边补 0

两个二进制数对应位有 1 则结果为 1，
相当于将两个数的二进制位合并

int A = 6;  // 二进制: 110
int B = 5;  // 二进制: 101

// 获取 B 的二进制长度
int lenB = Integer.toBinaryString(B).length();  // lenB = 3

// 方法1：使用数学公式
int result1 = A * (int)Math.pow(2, lenB) + B;  // 6 * 8 + 5 = 53

// 方法2：使用位运算
int result2 = (A << lenB) | B;  // (110 << 3) | 101 = 110000 | 101 = 110101

System.out.println("A: " + Integer.toBinaryString(A));      // 110
System.out.println("B: " + Integer.toBinaryString(B));      // 101
System.out.println("拼接结果: " + Integer.toBinaryString(result2));  // 110101
System.out.println("十进制: " + result2);  // 53

判断一个数是否为2的幂

逻辑:

2的幂的二进制表示只有一个1，其余都是0：按位与（&）的结果是0

1 = 0001
2 = 0010
4 = 0100
8 = 1000

示例：

1
2
3

n      = 8  = 1000  (二进制)
n - 1  = 7  = 0111
n & (n-1) = 1000 & 0111 = 0000 = 0

对应题目

连续连接二进制字符串数字

class Solution {
    private static final int MOD = 1000000007;

    public int concatenatedBinary(int n) {
        long result = 0;
        int shift = 0;  // 移位数
        for (int i = 1; i <= n; i++) {
            // 判断一个数是否为2的幂
            if ((i & (i - 1)) == 0) {
                shift++;
            }
            result = ((result << shift) | i) % MOD;
        }
        return (int) result;
    }
}