【性能优化】 - 位运算

宋 游戏开发
  2025-07-28 22:01:57 2025-07-28 22:01:57 创建   2025-07-28 22:33:59 2025-07-28 22:33:59 更新      1.5k 字  7 分钟

很久没有写博客了，最近工作用到位运算的地方有很多，也来学习一下，以后多多使用。

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

位运算相比普通算术运算（如加减乘除）具有以下核心优势，这些优势在性能敏感的场景中尤为重要：

1. 速度优势：直接由硬件底层支持

位运算的操作简单：按位与（&）、或（|）、异或（^）、移位（<<, >>）等操作通常只需1个时钟周期完成，而普通算术运算（如乘除法）需要更复杂的逻辑电路和多个时钟周期。
硬件加速：位运算直接作用于二进制位，CPU的ALU（算术逻辑单元）对位运算有专门优化。

2.内存效率：节省存储空间

布尔状态压缩：用单个整数的特定位表示多个布尔值（如权限标志、状态机）。例如：
仅需1个int（32位）即可存储32种独立状态，而传统布尔数组需要32字节。
位图（Bitmap）：用bit位存储大规模数据集合（如检测1000万个唯一ID是否存在），占用内存仅为1MB（1000万bit），而数组或哈希表可能需要数十倍空间。

3. 直接硬件控制：嵌入式与底层开发的核心工具
4. 代码简洁性与精确控制
5. 算法优化：解决特定问题的高效方案

下面提供一些位运算的常用算法作为工具类，希望自己以后也能多多使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <string>
#include <vector>
#include <numeric>
#include <bitset>

class BitUtils {
public:
    // 判断奇偶性
    static bool isEven(int n) {
        return (n & 1) == 0;
    }

    // 交换两个变量
    static void swap(int &a, int &b) {
        if (a != b) {
            a ^= b;
            b ^= a;
            a ^= b;
        }
    }

    // 简单加密/解密
    static std::string encryptDecrypt(const std::string &data, int key) {
        std::string result = data;
        for (size_t i = 0; i < result.size(); ++i) {
            result[i] = result[i] ^ key;
        }
        return result;
    }

    // 快速乘/除2的幂
    static int multiplyByPowerOfTwo(int n, int power) {
        return n << power;
    }
    
    static int divideByPowerOfTwo(int n, int power) {
        return n >> power;
    }

    // 存储多个布尔状态
    static int setFlag(int flags, int position, bool value) {
        if (value)
            return flags | (1 << position);
        else
            return flags & ~(1 << position);
    }

    // 设置特定位
    static int setBit(int n, int position) {
        return n | (1 << position);
    }

    // 按位取反
    static int invertBits(int n) {
        return ~n;
    }

    // 找出数组中唯一的单个数
    template <typename T>
    static T findUnique(const std::vector<T> &nums) {
        return std::accumulate(nums.begin(), nums.end(), T(0), 
                              [](T a, T b){ return a ^ b; });
    }

    // 无进位加法
    static int addWithoutCarry(int a, int b) {
        while (b != 0) {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }

    // 快速计算二进制中1的个数
    static int countSetBits(int n) {
        int count = 0;
        while (n) {
            n &= n - 1;
            ++count;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public static class BitUtils
{
    // 判断奇偶性
    public static bool IsEven(int n) => (n & 1) == 0;

    // 交换两个变量
    public static void Swap(ref int a, ref int b)
    {
        if (a != b)
        {
            a ^= b;
            b ^= a;
            a ^= b;
        }
    }

    // 简单加密/解密
    public static string EncryptDecrypt(string data, int key)
    {
        char[] result = new char[data.Length];
        for (int i = 0; i < data.Length; i++)
        {
            result[i] = (char)(data[i] ^ key);
        }
        return new string(result);
    }

    // 快速乘/除2的幂
    public static int MultiplyByPowerOfTwo(int n, int power) => n << power;
    public static int DivideByPowerOfTwo(int n, int power) => n >> power;

    // 存储多个布尔状态
    public static int SetFlag(int flags, int position, bool value)
    {
        return value ? flags | (1 << position) : flags & ~(1 << position);
    }

    // 设置特定位
    public static int SetBit(int n, int position) => n | (1 << position);

    // 按位取反
    public static int InvertBits(int n) => ~n;

    // 找出数组中唯一的单个数
    public static T FindUnique<T>(T[] nums)
    {
        dynamic result = 0;
        foreach (var num in nums)
        {
            result ^= num;
        }
        return result;
    }

    // 无进位加法
    public static int AddWithoutCarry(int a, int b)
    {
        while (b != 0)
        {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }

    // 快速计算二进制中1的个数
    public static int CountSetBits(int n)
    {
        int count = 0;
        while (n != 0)
        {
            n &= n - 1;
            count++;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class BitUtils {
    // 判断奇偶性
    static isEven(n: number): boolean {
        return (n & 1) === 0;
    }

    // 交换两个变量
    static swap(a: number, b: number): [number, number] {
        if (a === b) return [a, b];
        a ^= b;
        b ^= a;
        a ^= b;
        return [a, b];
    }

    // 简单加密/解密
    static encryptDecrypt(data: string, key: number): string {
        const arr = data.split('').map(c => String.fromCharCode(c.charCodeAt(0) ^ key));
        return arr.join('');
    }

    // 快速乘/除2的幂
    static multiplyByPowerOfTwo(n: number, power: number): number {
        return n << power;
    }
    
    static divideByPowerOfTwo(n: number, power: number): number {
        return n >> power;
    }

    // 存储多个布尔状态
    static setFlag(flags: number, position: number, value: boolean): number {
        return value ? flags | (1 << position) : flags & ~(1 << position);
    }

    // 设置特定位
    static setBit(n: number, position: number): number {
        return n | (1 << position);
    }

    // 按位取反
    static invertBits(n: number): number {
        return ~n;
    }

    // 找出数组中唯一的单个数
    static findUnique<T>(nums: T[]): T {
        return nums.reduce((a, b) => a ^ b as any, 0 as any);
    }

    // 无进位加法
    static addWithoutCarry(a: number, b: number): number {
        while (b !== 0) {
            let carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }

    // 快速计算二进制中1的个数
    static countSetBits(n: number): number {
        let count = 0;
        while (n) {
            n &= n - 1;
            count++;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
BitUtils = {}

-- 判断奇偶性
function BitUtils.is_even(n)
    return (n & 1) == 0
end

-- 交换两个变量
function BitUtils.swap(a, b)
    if a ~= b then
        a = a ~ b
        b = a ~ b
        a = a ~ b
    end
    return a, b
end

-- 简单加密/解密
function BitUtils.encrypt_decrypt(data, key)
    local result = {}
    for i = 1, #data do
        table.insert(result, string.char(bit32.bxor(string.byte(data, i), key)))
    end
    return table.concat(result)
end

-- 快速乘/除2的幂
function BitUtils.multiply_by_power_of_two(n, power)
    return n << power
end

function BitUtils.divide_by_power_of_two(n, power)
    return n >> power
end

-- 存储多个布尔状态
function BitUtils.set_flag(flags, position, value)
    if value then
        return flags | (1 << position)
    else
        return flags & bit32.bnot(1 << position)
    end
end

-- 设置特定位
function BitUtils.set_bit(n, position)
    return n | (1 << position)
end

-- 按位取反
function BitUtils.invert_bits(n)
    return ~n
end

-- 找出数组中唯一的单个数
function BitUtils.find_unique(nums)
    local result = 0
    for _, num in ipairs(nums) do
        result = result ~ num
    end
    return result
end

-- 无进位加法
function BitUtils.add_without_carry(a, b)
    while b ~= 0 do
        local carry = a & b
        a = a ~ b
        b = carry << 1
    end
    return a
end

-- 快速计算二进制中1的个数
function BitUtils.count_set_bits(n)
    local count = 0
    while n ~= 0 do
        n = n & (n - 1)
        count = count + 1
    end
    return count
end
  • 标题: 【性能优化】 - 位运算
  • 作者: 宋
  • 创建于 : 2025-07-28 22:01:57
  • 更新于 : 2025-07-28 22:33:59
  • 链接: https://sxl-space.tk/2025/07/28/006_BitWiseOperation/
  • 版权声明: 版权所有 © 宋，禁止转载。
目录
【性能优化】 - 位运算
  1. 1. 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。
    1. 1.1. 1. 速度优势：直接由硬件底层支持
    2. 1.2. 2.内存效率：节省存储空间
    3. 1.3. 3. 直接硬件控制：嵌入式与底层开发的核心工具
    4. 1.4. 4. 代码简洁性与精确控制
    5. 1.5. 5. 算法优化：解决特定问题的高效方案