位运算实用指南 🔧

一、为什么要学习位运算？ 🤔

在前端开发中，合理使用位运算可以：

• 提高代码执行效率
• 优化内存使用
• 简化某些数学运算
• 实现一些有趣的功能

二、位运算基础知识 ⚡

1. 常用位运算符

& (与)     // 两位都为1时才为1
| (或)     // 只要有一位为1就为1
^ (异或)   // 两位不同时为1
~ (取反)   // 0变1，1变0
<< (左移)  // 向左移动指定位数
>> (右移)  // 向右移动指定位数

三、经典问题解析 💡

1. 计算二进制中1的个数（汉明重量）

解法一：循环左移判断

while ((line = await readline())) {
    let res = 0;
    for (let i = 0; i < 32; i++) {
        // 利用1的循环左移和原数据进行与运算
        // 每次判断一个位置是否为1
        if ((line & (1 << i)) !== 0) {
            res++;
        }
    }
    console.log(res);
}

解法二：循环右移统计

while ((line = await readline())) {
    let res = 0;
    for (let i = 0; i < 32; i++) {
        // 每次取最低位判断是否为1
        res += (line & 1);
        // 右移一位，继续判断
        line >>= 1;
    }
    console.log(res);
}

解法三：巧用 n & (n-1)

while ((line = await readline())) {
    let res = 0;
    while (line != 0) {
        // n & (n-1) 可以消除最后一个1
        // 例如：110100 & 110011 = 110000
        line = line & (line - 1);
        res++;
    }
    console.log(res);
}

2. 不用加减乘除做加法

function Add(num1, num2) {
    while (num2 !== 0) {
        // 异或运算得到原位和
        const sum = num1 ^ num2;
        // 与运算后左移得到进位值
        const carry = (num1 & num2) << 1;
        
        num1 = sum;
        num2 = carry;
    }
    return num1;
}

// 使用示例
console.log(Add(5, 7));  // 12

3. 数组中只出现一次的两个数字

解法一：Map方法

function FindNumsAppearOnce(array) {
    // 使用Map记录每个数字出现的次数
    const map = new Map();
    array.forEach(x => {
        map.set(x, (map.get(x) || 0) + 1);
    });
    
    // 过滤出现次数为1的数字并排序
    return Array.from(map.keys())
        .filter(x => map.get(x) === 1)
        .sort((a, b) => a - b);
}

解法二：位运算法

function FindNumsAppearOnce(array) {
    // 1. 所有数字异或，得到两个单次出现数字的异或结果
    let xorResult = 0;
    array.forEach(num => {
        xorResult ^= num;
    });
    
    // 2. 找到异或结果中第一个为1的位置
    // 这个1表示两个目标数字在这一位上不同
    const mask = xorResult & (-xorResult);
    
    // 3. 根据这一位将数组分成两组
    let num1 = 0, num2 = 0;
    array.forEach(num => {
        if (num & mask) {
            num1 ^= num;  // 第一组
        } else {
            num2 ^= num;  // 第二组
        }
    });
    
    return [num1, num2].sort((a, b) => a - b);
}

// 使用示例
console.log(FindNumsAppearOnce([1,2,3,3,2,9]));  // [1,9]

4. 求1+2+3+...+n

解法一：利用短路运算

function Sum_Solution(n) {
    // 利用&&短路特性实现递归终止
    // n > 0为true时继续递归，为false时返回n
    n && (n += Sum_Solution(n - 1));
    return n;
}

解法二：利用位运算

function Sum_Solution(n) {
    // 使用公式：(n+1)*n/2
    // 除以2可以用右移1位代替
    return (n * (n + 1)) >> 1;
}

四、实战应用 🚀

1. 权限控制

class Permission {
    static READ = 1;     // 0001
    static WRITE = 2;    // 0010
    static UPDATE = 4;   // 0100
    static DELETE = 8;   // 1000
    
    constructor() {
        this.permission = 0;
    }
    
    // 添加权限
    addPermission(permission) {
        this.permission |= permission;
    }
    
    // 检查权限
    hasPermission(permission) {
        return (this.permission & permission) === permission;
    }
}

// 使用示例
const userPermission = new Permission();
userPermission.addPermission(Permission.READ | Permission.WRITE);
console.log(userPermission.hasPermission(Permission.READ));  // true

五、性能优化建议 ⚡

1. 使用位运算代替简单的数学运算：

   • 乘2：n << 1
   • 除2：n >> 1
   • 判断奇偶：n & 1
   • 取整：n >> 0

2. 注意事项：

   • 代码可读性优先
   • 添加清晰的注释
   • 考虑数值范围
   • 处理边界情况

六、练习题推荐 📝

1. LeetCode 136: 只出现一次的数字
2. LeetCode 137: 只出现一次的数字 II
3. LeetCode 260: 只出现一次的数字 III
4. LeetCode 338: 比特位计数

七、扩展阅读 📚

• JavaScript位运算详解
• 位运算在前端优化中的应用
• 位运算实战案例分析