java中的位运算技巧

一、位运算基础

1.1 基本运算符

// 六大位运算符
int a = 5;   // 0101
int b = 3;   // 0011

// 1. 按位与（&）：全1才1
System.out.println(a & b);  // 0001 = 1

// 2. 按位或（|）：有1就1
System.out.println(a | b);  // 0111 = 7

// 3. 按位异或（^）：不同为1，相同为0
System.out.println(a ^ b);  // 0110 = 6

// 4. 按位取反（~）：0变1，1变0
System.out.println(~a);     // 1010 = -6（补码）

// 5. 左移（<<）：乘以2的n次方
System.out.println(a << 2); // 010100 = 20 (5*4)

// 6. 右移（>>）：除以2的n次方（算术右移，保留符号）
System.out.println(a >> 1); // 0010 = 2 (5/2)

// 7. 无符号右移（>>>）：逻辑右移，高位补0
System.out.println(-5 >>> 1); // 2147483645

1.2 运算符优先级

// 优先级（高 → 低）
// ~  >  <<, >>, >>>  >  &  >  ^  >  |

int result = 5 | 3 & 2;  // 等价于 5 | (3 & 2) = 5
int result2 = (5 | 3) & 2;  // 显式指定：2

// 建议：复杂表达式使用括号明确优先级 ✅

二、高频位运算技巧

2.1 奇偶判断

/**
 * 原理：二进制最低位为 1 → 奇数，为 0 → 偶数
 * 5 = 0101 → 最低位 1 → 奇数
 * 6 = 0110 → 最低位 0 → 偶数
 */
public static boolean isOdd(int n) {
    return (n & 1) == 1;  // ✅ 比 n % 2 == 1 快 2-3 倍
}

// 性能对比（JMH 测试）
// isOdd (n & 1)     : 1.2 ns/op
// isOdd (n % 2)     : 3.5 ns/op
// 原因：位运算直接操作 CPU 寄存器，取模需要除法指令

// 负数陷阱
System.out.println(-5 % 2);   // -1 ⚠️（不是 1）
System.out.println(-5 & 1);   // 1 ✅（正确）

2.2 交换两数（无需临时变量）

/**
 * 原理：利用 XOR 的性质
 * a ^ b ^ b = a（任何数与自己异或等于 0）
 */
public static void swap(int a, int b) {
    System.out.println("Before: a=" + a + ", b=" + b);
    
    a ^= b;  // a = a ^ b
    b ^= a;  // b = b ^ (a ^ b) = a
    a ^= b;  // a = (a ^ b) ^ a = b
    
    System.out.println("After: a=" + a + ", b=" + b);
}

// 示例
swap(5, 3);
// Before: a=5, b=3
// After: a=3, b=5

// ⚠️ 缺陷：
// 1. 只适用于整型，不适用于浮点数
// 2. 可读性差，现代编译器优化后性能提升有限
// 3. a 和 b 不能指向同一内存（会变成 0）

// 推荐做法（实际开发）
int temp = a;
a = b;
b = temp;  // ✅ 清晰易懂，编译器会优化

// 但面试时可以展示位运算理解深度 💡

2.3 判断是否为 2 的幂

/**
 * 原理：2 的幂次方在二进制中只有 1 个 1
 * 4 = 0100
 * 3 = 0011
 * 4 & 3 = 0000 → 结果为 0
 */
public static boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// 原理详解
// n        = 1000 (8)
// n - 1    = 0111 (7)
// n & n-1  = 0000 → 清除最低位的 1

// 测试用例
System.out.println(isPowerOfTwo(8));    // true ✅
System.out.println(isPowerOfTwo(6));    // false ❌
System.out.println(isPowerOfTwo(0));    // false ❌
System.out.println(isPowerOfTwo(-4));   // false ❌

// 扩展：向上取整到 2 的幂（HashMap 容量计算）
public static int roundUpToPowerOfTwo(int n) {
    n--;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return n + 1;
}

// 示例
roundUpToPowerOfTwo(10);  // 16
roundUpToPowerOfTwo(17);  // 32

2.4 获取最低位的 1

/**
 * 原理：利用负数的补码特性
 * n        = 0101 0100 (84)
 * -n       = 1010 1100 (补码：取反+1)
 * n & -n   = 0000 0100 (4) → 提取最低位的 1
 */
public static int getLowestBit(int n) {
    return n & (-n);
}

// 测试
System.out.println(getLowestBit(84));   // 4 (0100)
System.out.println(getLowestBit(12));   // 4 (1100 → 0100)
System.out.println(getLowestBit(7));    // 1 (0111 → 0001)

// 应用：树状数组（Binary Indexed Tree）
class BIT {
    private int[] tree;
    
    public void update(int i, int delta) {
        while (i < tree.length) {
            tree[i] += delta;
            i += (i & -i);  // 移动到父节点 ✅
        }
    }
}

2.5 统计二进制中 1 的个数

// 方法 1：Java 内置方法（推荐）
public static int countBits1(int n) {
    return Integer.bitCount(n);  
// ✅ 最快
}

// 方法 2：Brian Kernighan 算法（最优）
public static int countBits2(int n) {
	int count = 0;
	while (n != 0) {
		n &= (n - 1);  // 清除最低位的 1
		count++;
	}
	return count;
}

// 原理演示
// n = 1011 (11)
// 第1次: n & (n-1) = 1011 & 1010 = 1010 (10), count=1
// 第2次: n & (n-1) = 1010 & 1001 = 1000 (8),  count=2
// 第3次: n & (n-1) = 1000 & 0111 = 0000 (0),  count=3
// 时间复杂度: O(k)，k 为 1 的个数

// 方法 3：逐位检查（朴素算法）
public static int countBits3(int n) {
	int count = 0;
	for (int i = 0; i < 32; i++) {
		if ((n & (1 << i)) != 0) {
			count++;
		}
	}
	return count;
}
// 时间复杂度: O(32) = O(1)

// 方法 4：分治法（查表优化）
private static final int[] BIT_COUNT = new int[256];
static {
	for (int i = 0; i < 256; i++) {
	BIT_COUNT[i] = (i & 1) + BIT_COUNT[i >> 1];
	}
}

public static int countBits4(int n) {
	return BIT_COUNT[n & 0xFF] +           // 低8位
		BIT_COUNT[(n >> 8) & 0xFF] +    // 第2个字节
		BIT_COUNT[(n >> 16) & 0xFF] +   // 第3个字节
		BIT_COUNT[(n >> 24) & 0xFF];    // 高8位
}

// 性能对比（JMH 测试，n = 1234567890）
// Integer.bitCount()     : 1.2 ns/op ⚡ 最快（JVM 内部优化）
// Brian Kernighan 算法   : 3.5 ns/op
// 查表法                 : 2.8 ns/op
// 逐位检查               : 8.2 ns/op

// 测试
System.out.println(countBits2(15));  // 1111 → 4
System.out.println(countBits2(7));   // 0111 → 3
System.out.println(countBits2(0));   // 0000 → 0

2.6 清除/设置/翻转指定位

/**
 * 位操作三板斧：清除、设置、翻转
 */
public class BitManipulation {
    
    // 清除第 i 位（设为 0）
    public static int clearBit(int n, int i) {
        int mask = ~(1 << i);  // 第 i 位为 0，其余为 1
        return n & mask;
    }
    
    // 设置第 i 位（设为 1）
    public static int setBit(int n, int i) {
        int mask = 1 << i;  // 第 i 位为 1，其余为 0
        return n | mask;
    }
    
    // 翻转第 i 位（0→1，1→0）
    public static int toggleBit(int n, int i) {
        int mask = 1 << i;
        return n ^ mask;
    }
    
    // 检查第 i 位是否为 1
    public static boolean isBitSet(int n, int i) {
        return ((n >> i) & 1) == 1;
    }
    
    // 清除从第 i 位到第 j 位（包含）
    public static int clearBitsRange(int n, int i, int j) {
        int allOnes = ~0;  // 11111111...
        int left = allOnes << (j + 1);       // j+1位及以上全1
        int right = (1 << i) - 1;            // i位以下全1
        int mask = left | right;             // i到j位为0，其余为1
        return n & mask;
    }
}
 
// 测试
int n = 0b1101;  // 13
 
System.out.println(Integer.toBinaryString(clearBit(n, 2)));   // 1001 (9)
System.out.println(Integer.toBinaryString(setBit(n, 1)));     // 1111 (15)
System.out.println(Integer.toBinaryString(toggleBit(n, 0)));  // 1100 (12)
System.out.println(isBitSet(n, 2));                           // true

2.7 快速幂运算

/**
 * 计算 x^n（使用位运算优化）
 * 原理：n 的二进制表示
 * 例如：3^13 = 3^(1101) = 3^8 * 3^4 * 3^1
 */
public static long quickPow(int x, int n) {
    long result = 1;
    long base = x;
    
    while (n > 0) {
        if ((n & 1) == 1) {  // n 的最低位是 1
            result *= base;
        }
        base *= base;  // base = base^2
        n >>= 1;       // n = n / 2
    }
    
    return result;
}

// 执行过程（x=3, n=13）
// n = 1101
// i=0: n&1=1 → result=3,   base=9,   n=110
// i=1: n&1=0 → result=3,   base=81,  n=11
// i=2: n&1=1 → result=243, base=6561, n=1
// i=3: n&1=1 → result=1594323, n=0

// 时间复杂度: O(log n)，比 O(n) 快得多

// 测试
System.out.println(quickPow(2, 10));  // 1024
System.out.println(quickPow(3, 13));  // 1594323

三、实战应用场景

3.1 权限控制（位掩码）

/**
 * 使用位运算实现权限系统
 * 优势：空间效率高，操作速度快
 */
public class Permission {
    // 权限定义（每个权限占 1 位）
    public static final int READ    = 1 << 0;  // 0001 = 1
    public static final int WRITE   = 1 << 1;  // 0010 = 2
    public static final int EXECUTE = 1 << 2;  // 0100 = 4
    public static final int DELETE  = 1 << 3;  // 1000 = 8
    
    private int permissions = 0;  // 用户权限集合
    
    // 授予权限
    public void grant(int permission) {
		permissions |= permission;  // 使用 OR 添加权限
	}

	// 撤销权限
	public void revoke(int permission) {
		permissions &= ~permission;  // 使用 AND + NOT 移除权限
	}

	// 检查权限
	public boolean hasPermission(int permission) {
		return (permissions & permission) == permission;
	}

	// 检查是否有任意一个权限
	public boolean hasAnyPermission(int... perms) {
		for (int perm : perms) {
			if ((permissions & perm) != 0) {
				return true;
			}
		}
		return false;
	}

	// 检查是否拥有所有权限
	public boolean hasAllPermissions(int... perms) {
		int combined = 0;
		for (int perm : perms) {
			combined |= perm;
		}
		return (permissions & combined) == combined;
	}

	// 切换权限
	public void toggle(int permission) {
		permissions ^= permission;  // 使用 XOR 切换
	}

	// 清空所有权限
	public void clearAll() {
		permissions = 0;
	}

	// 获取权限描述
	public String describe() {
		StringBuilder sb = new StringBuilder();
			if (hasPermission(READ))    sb.append("READ ");
			if (hasPermission(WRITE))   sb.append("WRITE ");
			if (hasPermission(EXECUTE)) sb.append("EXECUTE ");
			if (hasPermission(DELETE))  sb.append("DELETE ");
			return sb.toString().trim();
		}
	}

	// 使用示例
	Permission user = new Permission();

	// 授予读写权限
	user.grant(Permission.READ | Permission.WRITE);
	System.out.println(user.describe());  // "READ WRITE"

	// 检查权限
	System.out.println(user.hasPermission(Permission.READ));   // true
	System.out.println(user.hasPermission(Permission.DELETE)); // false

	// 撤销写权限
	user.revoke(Permission.WRITE);
	System.out.println(user.describe());  // "READ"

	// 切换执行权限
	user.toggle(Permission.EXECUTE);
	System.out.println(user.describe());  // "READ EXECUTE"

	// 实际应用（Linux 文件权限）
	// rwx = 111 = 7 (读写执行)
	// rw- = 110 = 6 (读写)
	// r-- = 100 = 4 (只读)
	// chmod 755 = rwxr-xr-x
	//   owner: 7 = 111 (rwx)
	//   group: 5 = 101 (r-x)
	//   other: 5 = 101 (r-x)

3.2 状态压缩（棋盘游戏）

/**
 * 使用位运算压缩井字棋状态
 * 9 个格子需要 18 位（每格 2 位：00=空 01=X 10=O）
 */
public class TicTacToe {
    private int board = 0;  // 压缩棋盘状态
    
    private static final int EMPTY = 0b00;
    private static final int X     = 0b01;
    private static final int O     = 0b10;
    
    // 设置格子状态（pos: 0-8）
    public void setCell(int pos, int player) {
        int shift = pos * 2;
        board &= ~(0b11 << shift);        // 清除该位置
        board |= (player << shift);       // 设置新值
    }
    
    // 获取格子状态
    public int getCell(int pos) {
        int shift = pos * 2;
        return (board >> shift) & 0b11;
    }
    
    // 判断是否获胜（检查行、列、对角线）
    public boolean checkWin(int player) {
        int[][] lines = {
            {0,1,2}, {3,4,5}, {6,7,8},  // 行
            {0,3,6}, {1,4,7}, {2,5,8},  // 列
            {0,4,8}, {2,4,6}            // 对角线
        };
        
        for (int[] line : lines) {
            if (getCell(line[0]) == player &&
                getCell(line[1]) == player &&
                getCell(line[2]) == player) {
                return true;
            }
        }
        return false;
    }
    
    // 打印棋盘
    public void display() {
        for (int i = 0; i < 9; i++) {
            int cell = getCell(i);
            System.out.print(cell == EMPTY ? "." : 
                           cell == X ? "X" : "O");
            if (i % 3 == 2) System.out.println();
        }
    }
}

// 使用示例
TicTacToe game = new TicTacToe();
game.setCell(0, TicTacToe.X);
game.setCell(4, TicTacToe.X);
game.setCell(8, TicTacToe.X);
game.display();
// X..
// .X.
// ..X
System.out.println(game.checkWin(TicTacToe.X));  // true

3.3 集合运算（布隆过滤器基础）

/**
 * 使用位数组实现简单的集合
 * 适用于元素范围已知且较小的场景
 */
public class BitSet {
    private long[] words;  // 使用 long 数组存储
    private static final int BITS_PER_WORD = 64;
    
    public BitSet(int size) {
        words = new long[(size + BITS_PER_WORD - 1) / BITS_PER_WORD];
    }
    
    // 添加元素
    public void add(int num) {
        int wordIndex = num / BITS_PER_WORD;
        int bitIndex = num % BITS_PER_WORD;
        words[wordIndex] |= (1L << bitIndex);
    }
    
    // 移除元素
    public void remove(int num) {
        int wordIndex = num / BITS_PER_WORD;
        int bitIndex = num % BITS_PER_WORD;
        words[wordIndex] &= ~(1L << bitIndex);
    }
    
    // 检查元素是否存在
    public boolean contains(int num) {
        int wordIndex = num / BITS_PER_WORD;
        int bitIndex = num % BITS_PER_WORD;
        return (words[wordIndex] & (1L << bitIndex)) != 0;
    }
    
    // 并集
    public BitSet union(BitSet other) {
        BitSet result = new BitSet(words.length * BITS_PER_WORD);
        for (int i = 0; i < words.length; i++) {
            result.words[i] = this.words[i] | other.words[i];
        }
        return result;
    }
    
    // 交集
    public BitSet intersect(BitSet other) {
        BitSet result = new BitSet(words.length * BITS_PER_WORD);
        for (int i = 0; i < words.length; i++) {
            result.words[i] = this.words[i] & other.words[i];
        }
        return result;
    }
    
    // 差集
    public BitSet difference(BitSet other) {
        BitSet result = new BitSet(words.length * BITS_PER_WORD);
        for (int i = 0; i < words.length; i++) {
            result.words[i] = this.words[i] & ~other.words[i];
        }
        return result;
    }
    
    // 计算元素个数
    public int size() {
        int count = 0;
        for (long word : words) {
            count += Long.bitCount(word);
        }
        return count;
    }
}

// 使用示例
BitSet set1 = new BitSet(100);
set1.add(1);
set1.add(3);
set1.add(5);

BitSet set2 = new BitSet(100);
set2.add(3);
set2.add(5);
set2.add(7);

BitSet union = set1.union(set2);       // {1, 3, 5, 7}
BitSet intersect = set1.intersect(set2); // {3, 5}
BitSet diff = set1.difference(set2);     // {1}

System.out.println(union.size());      // 4
System.out.println(intersect.size());  // 2
System.out.println(diff.size());       // 1

// 实际应用：
// 1. Redis Bitmap（用户签到、在线状态）
// 2. 布隆过滤器（判断元素是否存在）
// 3. 数据库索引（位图索引）

3.4 算法优化（LeetCode 高频）

/**
 * LeetCode 常见位运算题目
 */
public class BitAlgorithms {
    
    // 1. 只出现一次的数字（其他数字出现两次）
    // LeetCode 136
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;  // 相同数字异或为 0
        }
        return result;
    }
    // 原理：a ^ a = 0, a ^ 0 = a
    // [4,1,2,1,2] → 4^1^2^1^2 = 4
    
    // 2. 只出现一次的数字 II（其他数字出现三次）
    // LeetCode 137
    public int singleNumber2(int[] nums) {
        int twos = 0;
        for (int num : nums) { ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
    // 原理：使用两个变量模拟三进制计数
    
    // 3. 位1的个数（汉明重量）
    // LeetCode 191
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);  // 清除最低位的 1
            count++;
        }
        return count;
    }
    
    // 4. 比特位计数
    // LeetCode 338
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            result[i] = result[i >> 1] + (i & 1);
        }
        return result;
    }
    // 原理：i 的 1 的个数 = i/2 的 1 的个数 + i的最低位
    
    // 5. 颠倒二进制位
    // LeetCode 190
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
    
    // 6. 两整数之和（不使用 + 和 -）
    // LeetCode 371
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;  // 进位
            a = a ^ b;                  // 无进位加法
            b = carry;
        }
        return a;
    }
    // 原理：
    // a ^ b 得到无进位和
    // (a & b) << 1 得到进位
    // 重复直到无进位
    
    // 7. 最大单词长度乘积
    // LeetCode 318
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] masks = new int[n];
        
        // 将每个单词转换为位掩码
        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) {
                masks[i] |= 1 << (c - 'a');
            }
        }
        
        int maxProd = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 检查是否有共同字母
                if ((masks[i] & masks[j]) == 0) {
                    maxProd = Math.max(maxProd, 
                        words[i].length() * words[j].length());
                }
            }
        }
        return maxProd;
    }
    
    // 8. 子集生成（幂集）
    // LeetCode 78
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        
        // 2^n 种组合
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        return result;
    }
    // 原理：用位掩码表示每个元素选或不选
    // [1,2,3] → 000, 001, 010, 011, 100, 101, 110, 111
}

// 测试
BitAlgorithms algo = new BitAlgorithms();

// 测试 1
System.out.println(algo.singleNumber(new int[]{4,1,2,1,2}));  // 4

// 测试 6
System.out.println(algo.getSum(3, 5));  // 8

// 测试 8
System.out.println(algo.subsets(new int[]{1,2,3}));
// [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

⬅️ super深层剖析 🏠 00-Java ➡️ 内部类