Go math/bits 包详解

概述

math/bits 包实现了预声明的无符号整数类型的位计数和操作函数。该包提供了高效的底层位操作功能，包括位计数、位旋转、位长度计算、加减乘除运算等。包中的函数可能被编译器直接实现以获得更好的性能。

重要说明：

• ✓ 仅适用于无符号整数类型（uint8、uint16、uint32、uint64、uint）
• ✓ 函数执行时间是常数时间，不依赖于输入值
• ✓ 编译器可能直接实现这些函数以获得更好性能
• ✓ 适用于加密、图像处理、数据压缩等场景
• ✓ Go 1.9+ 引入

包导入

import "math/bits"

基本使用

1. 位计数操作

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    x := uint8(0b11010010)
    
    // 计算 1 的个数
    fmt.Printf("OnesCount(%08b) = %d\n", x, bits.OnesCount8(x))
    
    // 前导零的个数
    fmt.Printf("LeadingZeros(%08b) = %d\n", x, bits.LeadingZeros8(x))
    
    // 末尾零的个数
    fmt.Printf("TrailingZeros(%08b) = %d\n", x, bits.TrailingZeros8(x))
}

2. 位旋转操作

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    x := uint8(0b00001111)
    
    // 左旋 2 位
    rotated := bits.RotateLeft8(x, 2)
    fmt.Printf("RotateLeft8(%08b, 2) = %08b\n", x, rotated)
    
    // 右旋 2 位（等同于左旋 -2）
    rotated = bits.RotateLeft8(x, -2)
    fmt.Printf("RotateLeft8(%08b, -2) = %08b\n", x, rotated)
}

3. 多精度算术运算

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // 64 位加法带进位
    x, y := uint64(1<<63), uint64(1<<63)
    hi, lo := bits.Add64(x, y, 0)
    fmt.Printf("Add64(%d, %d, 0) = (hi=%d, lo=%d)\n", x, y, hi, lo)
    
    // 64 位乘法
    hi, lo = bits.Mul64(x, 2)
    fmt.Printf("Mul64(%d, 2) = (hi=%d, lo=%d)\n", x, hi, lo)
}

一、常量

UintSize

定义：

const UintSize = uintSize

说明：

• 功能：uint 类型的位数
• 值：32 或 64（取决于架构）
• 用途：用于确定当前平台的 uint 大小

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    fmt.Printf("当前平台 uint 是 %d 位\n", bits.UintSize)
    // 输出：当前平台 uint 是 64 位（64 位系统）
    // 或：当前平台 uint 是 32 位（32 位系统）
}

二、加法函数

Add

定义：

func Add(x, y, carry uint) (sum, carryOut uint)

说明：

• 功能：带进位的加法：sum = x + y + carry
• 参数：
  • x, y - 加数
  • carry - 进位（必须是 0 或 1）
• 返回值：
  • sum - 和
  • carryOut - 进位输出（0 或 1）
• 特点：常数时间执行

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // 简单加法
    sum, carry := bits.Add(10, 20, 0)
    fmt.Printf("Add(10, 20, 0) = (%d, %d)\n", sum, carry)
    
    // 带进位
    sum, carry = bits.Add(10, 20, 1)
    fmt.Printf("Add(10, 20, 1) = (%d, %d)\n", sum, carry)
    
    // 溢出示例
    x, y := uint(^uint(0)>>1), uint(2)
    sum, carry = bits.Add(x, y, 0)
    fmt.Printf("Add(%d, %d, 0) = (%d, %d)\n", x, y, sum, carry)
}

Add32

定义：

func Add32(x, y, carry uint32) (sum, carryOut uint32)

说明：

• 功能：32 位带进位加法
• 参数：x, y, carry - uint32 类型
• 返回值：sum, carryOut - uint32 类型

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // [33 12] + [21 23] = [54 35]
    lo1, hi1 := uint32(12), uint32(33)
    lo2, hi2 := uint32(23), uint32(21)
    
    sum, carry := bits.Add32(lo1, lo2, 0)
    hi, carry2 := bits.Add32(hi1, hi2, carry)
    
    fmt.Printf("[%d %d] + [%d %d] = [%d %d] (carry=%d)\n", 
        hi1, lo1, hi2, lo2, hi, sum, carry2)
}

Add64

定义：

func Add64(x, y, carry uint64) (sum, carryOut uint64)

说明：

• 功能：64 位带进位加法
• 参数：x, y, carry - uint64 类型
• 返回值：sum, carryOut - uint64 类型

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // 大数加法
    x := uint64(1<<63 - 1)
    y := uint64(1<<63 - 1)
    
    sum, carry := bits.Add64(x, y, 0)
    fmt.Printf("Add64(%d, %d, 0) = (%d, %d)\n", x, y, sum, carry)
}

三、减法函数

Sub

定义：

func Sub(x, y, borrow uint) (diff, borrowOut uint)

说明：

• 功能：带借位的减法：diff = x - y - borrow
• 参数：
  • x, y - 操作数
  • borrow - 借位（必须是 0 或 1）
• 返回值：
  • diff - 差
  • borrowOut - 借位输出（0 或 1）
• 特点：常数时间执行

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // 简单减法
    diff, borrow := bits.Sub(20, 10, 0)
    fmt.Printf("Sub(20, 10, 0) = (%d, %d)\n", diff, borrow)
    
    // 借位示例
    diff, borrow = bits.Sub(10, 20, 0)
    fmt.Printf("Sub(10, 20, 0) = (%d, %d)\n", diff, borrow)
    
    // 带借位
    diff, borrow = bits.Sub(10, 20, 1)
    fmt.Printf("Sub(10, 20, 1) = (%d, %d)\n", diff, borrow)
}

Sub32

定义：

func Sub32(x, y, borrow uint32) (diff, borrowOut uint32)

说明：

• 功能：32 位带借位减法

Sub64

定义：

func Sub64(x, y, borrow uint64) (diff, borrowOut uint64)

说明：

• 功能：64 位带借位减法

四、乘法函数

Mul

定义：

func Mul(x, y uint) (hi, lo uint)

说明：

• 功能：完整的乘法：(hi, lo) = x * y
• 参数：x, y - 乘数
• 返回值：
  • hi - 结果的高位部分
  • lo - 结果的低位部分
• 特点：返回完整的双倍宽度结果

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // 小数字乘法
    hi, lo := bits.Mul(10, 20)
    fmt.Printf("Mul(10, 20) = (hi=%d, lo=%d)\n", hi, lo)
    
    // 大数字乘法（会溢出）
    x := uint(^uint(0))
    hi, lo = bits.Mul(x, 2)
    fmt.Printf("Mul(%d, 2) = (hi=%d, lo=%d)\n", x, hi, lo)
}

Mul32

定义：

func Mul32(x, y uint32) (hi, lo uint32)

说明：

• 功能：32 位完整乘法
• 返回值：64 位结果的高 32 位和低 32 位

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // 2^31 * 2 = 2^32
    x := uint32(1 << 31)
    hi, lo := bits.Mul32(x, 2)
    fmt.Printf("Mul32(%d, 2) = (hi=%d, lo=%d)\n", x, hi, lo)
    // 输出：hi=1, lo=0 (结果是 2^32)
}

Mul64

定义：

func Mul64(x, y uint64) (hi, lo uint64)

说明：

• 功能：64 位完整乘法
• 返回值：128 位结果的高 64 位和低 64 位

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // 2^63 * 2 = 2^64
    x := uint64(1 << 63)
    hi, lo := bits.Mul64(x, 2)
    fmt.Printf("Mul64(%d, 2) = (hi=%d, lo=%d)\n", x, hi, lo)
    // 输出：hi=1, lo=0 (结果是 2^64)
}

五、除法函数

Div

定义：

func Div(hi, lo, y uint) (quo, rem uint)

说明：

• 功能：双倍宽度除法：quo = (hi, lo) / y, rem = (hi, lo) % y
• 参数：
  • hi - 被除数的高位
  • lo - 被除数的低位
  • y - 除数
• 返回值：
  • quo - 商
  • rem - 余数
• 注意：y == 0 或 y <= hi 时会 panic

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    // 简单除法
    quo, rem := bits.Div(0, 100, 7)
    fmt.Printf("Div(0, 100, 7) = (quo=%d, rem=%d)\n", quo, rem)
    
    // 双倍宽度除法
    hi, lo := uint(0), uint(1000)
    quo, rem = bits.Div(hi, lo, 30)
    fmt.Printf("%d / %d = %d 余 %d\n", lo, uint(30), quo, rem)
}

Div32

定义：

func Div32(hi, lo, y uint32) (quo, rem uint32)

说明：

• 功能：32 位双倍宽度除法
• 注意：y == 0 或 y <= hi 时会 panic

Div64

定义：

func Div64(hi, lo, y uint64) (quo, rem uint64)

说明：

• 功能：64 位双倍宽度除法
• 注意：y == 0 或 y <= hi 时会 panic

六、取余函数

Rem

定义：

func Rem(hi, lo, y uint) uint

说明：

• 功能：返回 (hi, lo) % y 的余数
• 参数：hi, lo - 被除数，y - 除数
• 返回值：余数
• 注意：y == 0 或 y <= hi 时会 panic

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    rem := bits.Rem(0, 100, 7)
    fmt.Printf("Rem(0, 100, 7) = %d\n", rem) // 2
}

Rem32

定义：

func Rem32(hi, lo, y uint32) uint32

说明：

• 功能：32 位取余

Rem64

定义：

func Rem64(hi, lo, y uint64) uint64

说明：

• 功能：64 位取余

七、前导零计数函数

LeadingZeros

定义：

func LeadingZeros(x uint) int

说明：

• 功能：返回 x 的前导零个数
• 参数：x - 无符号整数
• 返回值：前导零数量
• 特殊情况：x == 0 时返回 UintSize

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    x := uint8(0b00001000)
    fmt.Printf("LeadingZeros8(%08b) = %d\n", x, bits.LeadingZeros8(x))
    
    x = 0
    fmt.Printf("LeadingZeros8(%08b) = %d\n", x, bits.LeadingZeros8(x))
}

LeadingZeros8

定义：

func LeadingZeros8(x uint8) int

说明：

• 功能：返回 uint8 的前导零个数
• 返回值：0-8

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    for i := 0; i < 8; i++ {
        x := uint8(1 << i)
        fmt.Printf("LeadingZeros8(%08b) = %d\n", x, bits.LeadingZeros8(x))
    }
}

LeadingZeros16

定义：

func LeadingZeros16(x uint16) int

说明：

• 功能：返回 uint16 的前导零个数
• 返回值：0-16

LeadingZeros32

定义：

func LeadingZeros32(x uint32) int

说明：

• 功能：返回 uint32 的前导零个数
• 返回值：0-32

LeadingZeros64

定义：

func LeadingZeros64(x uint64) int

说明：

• 功能：返回 uint64 的前导零个数
• 返回值：0-64

八、位长度函数

Len

定义：

func Len(x uint) int

说明：

• 功能：返回表示 x 所需的最小位数
• 参数：x - 无符号整数
• 返回值：位数
• 特殊情况：x == 0 时返回 0
• 关系：Len(x) = UintSize - LeadingZeros(x)

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    fmt.Printf("Len(0) = %d\n", bits.Len(0))
    fmt.Printf("Len(1) = %d\n", bits.Len(1))
    fmt.Printf("Len(7) = %d\n", bits.Len(7))    // 111 = 3 位
    fmt.Printf("Len(8) = %d\n", bits.Len(8))    // 1000 = 4 位
    fmt.Printf("Len(255) = %d\n", bits.Len(255)) // 11111111 = 8 位
}

Len8

定义：

func Len8(x uint8) int

说明：

• 功能：返回表示 uint8 所需的最小位数
• 返回值：0-8

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    fmt.Printf("Len8(%08b) = %d\n", 8, bits.Len8(8)) // 00001000 = 4
}

Len16

定义：

func Len16(x uint16) int

说明：

• 功能：返回表示 uint16 所需的最小位数
• 返回值：0-16

Len32

定义：

func Len32(x uint32) int

说明：

• 功能：返回表示 uint32 所需的最小位数
• 返回值：0-32

Len64

定义：

func Len64(x uint64) int

说明：

• 功能：返回表示 uint64 所需的最小位数
• 返回值：0-64

九、1 的计数函数

OnesCount

定义：

func OnesCount(x uint) int

说明：

• 功能：返回 x 中 1 的个数（人口计数）
• 参数：x - 无符号整数
• 返回值：1 的数量
• 用途：数据压缩、加密、校验等

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    x := uint(0b11010010)
    fmt.Printf("OnesCount(%b) = %d\n", x, bits.OnesCount(x))
    
    // 应用：计算汉明距离
    a, b := uint(0b1100), uint(0b1010)
    distance := bits.OnesCount(a ^ b)
    fmt.Printf("汉明距离 (%b, %b) = %d\n", a, b, distance)
}

OnesCount8

定义：

func OnesCount8(x uint8) int

说明：

• 功能：返回 uint8 中 1 的个数

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    fmt.Printf("OnesCount8(%08b) = %d\n", 14, bits.OnesCount8(14)) // 00001110 = 3
}

OnesCount16

定义：

func OnesCount16(x uint16) int

说明：

• 功能：返回 uint16 中 1 的个数

OnesCount32

定义：

func OnesCount32(x uint32) int

说明：

• 功能：返回 uint32 中 1 的个数

OnesCount64

定义：

func OnesCount64(x uint64) int

说明：

• 功能：返回 uint64 中 1 的个数

十、末尾零计数函数

TrailingZeros

定义：

func TrailingZeros(x uint) int

说明：

• 功能：返回 x 的末尾零个数
• 参数：x - 无符号整数
• 返回值：末尾零数量
• 特殊情况：x == 0 时返回 UintSize
• 用途：快速找到最低位的 1

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    for i := 0; i < 8; i++ {
        x := uint8(1 << i)
        fmt.Printf("TrailingZeros8(%08b) = %d\n", x, bits.TrailingZeros8(x))
    }
    
    // 应用：找到最低位的 1
    x := uint8(0b00100100)
    tz := bits.TrailingZeros8(x)
    fmt.Printf("最低位的 1 在第 %d 位\n", tz)
}

TrailingZeros8

定义：

func TrailingZeros8(x uint8) int

说明：

• 功能：返回 uint8 的末尾零个数
• 返回值：0-8

TrailingZeros16

定义：

func TrailingZeros16(x uint16) int

说明：

• 功能：返回 uint16 的末尾零个数
• 返回值：0-16

TrailingZeros32

定义：

func TrailingZeros32(x uint32) int

说明：

• 功能：返回 uint32 的末尾零个数
• 返回值：0-32

TrailingZeros64

定义：

func TrailingZeros64(x uint64) int

说明：

• 功能：返回 uint64 的末尾零个数
• 返回值：0-64

十一、位反转函数

Reverse

定义：

func Reverse(x uint) uint

说明：

• 功能：反转 x 的位顺序
• 参数：x - 无符号整数
• 返回值：位反转后的值

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    x := uint8(0b11000000)
    fmt.Printf("Reverse8(%08b) = %08b\n", x, bits.Reverse8(x))
    // 输出：Reverse8(11000000) = 00000011
}

Reverse8

定义：

func Reverse8(x uint8) uint8

说明：

• 功能：反转 uint8 的位顺序

Reverse16

定义：

func Reverse16(x uint16) uint16

说明：

• 功能：反转 uint16 的位顺序

Reverse32

定义：

func Reverse32(x uint32) uint32

说明：

• 功能：反转 uint32 的位顺序

Reverse64

定义：

func Reverse64(x uint64) uint64

说明：

• 功能：反转 uint64 的位顺序

十二、字节反转函数

ReverseBytes

定义：

func ReverseBytes(x uint) uint

说明：

• 功能：反转 x 的字节顺序（字节端序转换）
• 参数：x - 无符号整数
• 返回值：字节反转后的值
• 用途：大端序和小端序转换

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    x := uint32(0x12345678)
    fmt.Printf("ReverseBytes32(0x%08X) = 0x%08X\n", x, bits.ReverseBytes32(x))
    // 输出：ReverseBytes32(0x12345678) = 0x78563412
}

ReverseBytes16

定义：

func ReverseBytes16(x uint16) uint16

说明：

• 功能：反转 uint16 的字节顺序

ReverseBytes32

定义：

func ReverseBytes32(x uint32) uint32

说明：

• 功能：反转 uint32 的字节顺序

ReverseBytes64

定义：

func ReverseBytes64(x uint64) uint64

说明：

• 功能：反转 uint64 的字节顺序

十三、位旋转函数

RotateLeft

定义：

func RotateLeft(x uint, k int) uint

说明：

• 功能：将 x 左旋转 k 位
• 参数：
  • x - 无符号整数
  • k - 旋转位数（负数表示右旋）
• 返回值：旋转后的值
• 特点：循环旋转，移出的位从另一端进入

示例：

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    x := uint8(0b00001111)
    
    // 左旋 2 位
    r := bits.RotateLeft8(x, 2)
    fmt.Printf("RotateLeft8(%08b, 2) = %08b\n", x, r)
    
    // 右旋 2 位（等同于左旋 -2）
    r = bits.RotateLeft8(x, -2)
    fmt.Printf("RotateLeft8(%08b, -2) = %08b\n", x, r)
    
    // 验证循环
    r = bits.RotateLeft8(x, 8)
    fmt.Printf("RotateLeft8(%08b, 8) = %08b (回到原值)\n", x, r)
}

RotateLeft8

定义：

func RotateLeft8(x uint8, k int) uint8

说明：

• 功能：将 uint8 左旋转 k 位
• 旋转：k mod 8 位

RotateLeft16

定义：

func RotateLeft16(x uint16, k int) uint16

说明：

• 功能：将 uint16 左旋转 k 位
• 旋转：k mod 16 位

RotateLeft32

定义：

func RotateLeft32(x uint32, k int) uint32

说明：

• 功能：将 uint32 左旋转 k 位
• 旋转：k mod 32 位

RotateLeft64

定义：

func RotateLeft64(x uint64, k int) uint64

说明：

• 功能：将 uint64 左旋转 k 位
• 旋转：k mod 64 位

十四、典型示例

示例 1：位操作基础

package main

import (
    "fmt"
    "math/bits"
)

func main() {
    x := uint8(0b11010010)
    
    fmt.Printf("数字：%08b (%d)\n\n", x, x)
    
    // 位计数
    fmt.Printf("OnesCount:     %d\n", bits.OnesCount8(x))
    fmt.Printf("LeadingZeros:  %d\n", bits.LeadingZeros8(x))
    fmt.Printf("TrailingZeros: %d\n", bits.TrailingZeros8(x))
    fmt.Printf("Len:           %d\n\n", bits.Len8(x))
    
    // 位变换
    fmt.Printf("Reverse:       %08b\n", bits.Reverse8(x))
    fmt.Printf("RotateLeft 2:  %08b\n", bits.RotateLeft8(x, 2))
    fmt.Printf("RotateLeft -2: %08b\n", bits.RotateLeft8(x, -2))
}

示例 2：多精度算术

package main

import (
    "fmt"
    "math/bits"
)

// 128 位加法
func add128(ah, al, bh, bl uint64) (uint64, uint64) {
    sum, carry := bits.Add64(al, bl, 0)
    hi, _ := bits.Add64(ah, bh, carry)
    return hi, sum
}

// 128 位减法
func sub128(ah, al, bh, bl uint64) (uint64, uint64) {
    diff, borrow := bits.Sub64(al, bl, 0)
    hi, _ := bits.Sub64(ah, bh, borrow)
    return hi, diff
}

// 128 位乘法
func mul128(a, b uint64) (uint64, uint64) {
    return bits.Mul64(a, b)
}

func main() {
    // 128 位加法
    ah, al := uint64(1), uint64(0)
    bh, bl := uint64(1), uint64(0)
    hi, lo := add128(ah, al, bh, bl)
    fmt.Printf("2^64 + 2^64 = (%d, %d)\n", hi, lo)
    
    // 128 位乘法
    hi, lo = mul128(1<<63, 2)
    fmt.Printf("2^63 * 2 = (%d, %d)\n", hi, lo)
}

示例 3：汉明距离计算

package main

import (
    "fmt"
    "math/bits"
)

// 计算两个数的汉明距离（不同位的数量）
func hammingDistance(a, b uint64) int {
    return bits.OnesCount64(a ^ b)
}

func main() {
    a, b := uint64(0b1100), uint64(0b1010)
    distance := hammingDistance(a, b)
    fmt.Printf("汉明距离 (%b, %b) = %d\n", a, b, distance)
    
    // 应用：比较两个字符串的相似度
    s1 := "hello"
    s2 := "hallo"
    
    var diff uint64
    for i := 0; i < len(s1) && i < len(s2); i++ {
        diff |= uint64(s1[i] ^ s2[i]) << (i * 8)
    }
    
    fmt.Printf("'%s' vs '%s' 的位差异：%d\n", s1, s2, bits.OnesCount64(diff))
}

示例 4：快速找到最低位的 1

package main

import (
    "fmt"
    "math/bits"
)

// 找到并清除最低位的 1
func clearLowestBit(x uint64) uint64 {
    return x & (x - 1)
}

// 提取最低位的 1
func extractLowestBit(x uint64) uint64 {
    return x & -x
}

func main() {
    x := uint64(0b00100100)
    
    // 找到最低位 1 的位置
    pos := bits.TrailingZeros64(x)
    fmt.Printf("最低位的 1 在第 %d 位\n", pos)
    
    // 提取最低位的 1
    lowest := extractLowestBit(x)
    fmt.Printf("extractLowestBit(%b) = %b\n", x, lowest)
    
    // 清除最低位的 1
    cleared := clearLowestBit(x)
    fmt.Printf("clearLowestBit(%b) = %b\n", x, cleared)
    
    // 应用：计算 1 的个数
    count := 0
    temp := x
    for temp != 0 {
        temp = clearLowestBit(temp)
        count++
    }
    fmt.Printf("1 的个数：%d (验证：%d)\n", count, bits.OnesCount64(x))
}

示例 5：字节序转换

package main

import (
    "encoding/binary"
    "fmt"
    "math/bits"
)

func main() {
    // 32 位字节序转换
    x := uint32(0x12345678)
    
    // 使用 bits.ReverseBytes
    reversed := bits.ReverseBytes32(x)
    fmt.Printf("ReverseBytes32(0x%08X) = 0x%08X\n", x, reversed)
    
    // 对比 encoding/binary
    bytes := make([]byte, 4)
    binary.BigEndian.PutUint32(bytes, x)
    fromBE := binary.LittleEndian.Uint32(bytes)
    fmt.Printf("LittleEndian(0x%08X) = 0x%08X\n", x, fromBE)
    
    // 验证
    fmt.Printf("结果相同：%v\n", reversed == fromBE)
}

示例 6：位图操作

package main

import (
    "fmt"
    "math/bits"
)

type BitSet []uint64

func NewBitSet(size int) BitSet {
    return make(BitSet, (size+63)/64)
}

func (bs BitSet) Set(pos int) {
    bs[pos/64] |= 1 << uint(pos%64)
}

func (bs BitSet) Clear(pos int) {
    bs[pos/64] &^= 1 << uint(pos%64)
}

func (bs BitSet) Get(pos int) bool {
    return bs[pos/64]&(1<<uint(pos%64)) != 0
}

func (bs BitSet) Count() int {
    count := 0
    for _, word := range bs {
        count += bits.OnesCount64(word)
    }
    return count
}

func (bs BitSet) FindFirst() int {
    for i, word := range bs {
        if word != 0 {
            return i*64 + bits.TrailingZeros64(word)
        }
    }
    return -1
}

func main() {
    bs := NewBitSet(128)
    
    // 设置一些位
    bs.Set(5)
    bs.Set(10)
    bs.Set(70)
    bs.Set(100)
    
    fmt.Printf("总位数：%d\n", bs.Count())
    fmt.Printf("第一个设置的位：%d\n", bs.FindFirst())
    fmt.Printf("位置 5: %v\n", bs.Get(5))
    fmt.Printf("位置 6: %v\n", bs.Get(6))
}

示例 7：加密算法中的位旋转

package main

import (
    "fmt"
    "math/bits"
)

// 简化的加密函数（仅用于演示）
func encrypt(value uint32, key uint32, rounds int) uint32 {
    state := value ^ key
    
    for i := 0; i < rounds; i++ {
        // 位旋转
        state = bits.RotateLeft32(state, 7)
        // 异或
        state ^= key
        // 再次旋转
        state = bits.RotateLeft32(state, 13)
    }
    
    return state
}

func decrypt(value uint32, key uint32, rounds int) uint32 {
    state := value
    
    for i := 0; i < rounds; i++ {
        // 逆向操作
        state = bits.RotateLeft32(state, -13)
        state ^= key
        state = bits.RotateLeft32(state, -7)
    }
    
    return state ^ key
}

func main() {
    plaintext := uint32(0x12345678)
    key := uint32(0xDEADBEEF)
    rounds := 3
    
    ciphertext := encrypt(plaintext, key, rounds)
    decrypted := decrypt(ciphertext, key, rounds)
    
    fmt.Printf("明文：0x%08X\n", plaintext)
    fmt.Printf("密文：0x%08X\n", ciphertext)
    fmt.Printf("解密：0x%08X\n", decrypted)
    fmt.Printf("解密成功：%v\n", plaintext == decrypted)
}

示例 8：性能优化对比

package main

import (
    "fmt"
    "math/bits"
    "time"
)

// 传统方法计算 1 的个数
func onesCountTraditional(x uint64) int {
    count := 0
    for x != 0 {
        count += int(x & 1)
        x >>= 1
    }
    return count
}

// 使用 bits.OnesCount64
func onesCountBits(x uint64) int {
    return bits.OnesCount64(x)
}

func main() {
    x := uint64(0x123456789ABCDEF0)
    iterations := 1000000
    
    // 传统方法
    start := time.Now()
    for i := 0; i < iterations; i++ {
        _ = onesCountTraditional(x)
    }
    traditionalTime := time.Since(start)
    
    // bits 方法
    start = time.Now()
    for i := 0; i < iterations; i++ {
        _ = onesCountBits(x)
    }
    bitsTime := time.Since(start)
    
    fmt.Printf("传统方法：%v\n", traditionalTime)
    fmt.Printf("bits 方法：%v\n", bitsTime)
    fmt.Printf("性能提升：%.2f 倍\n", float64(traditionalTime)/float64(bitsTime))
}

十五、最佳实践

1. 使用合适的类型

// ✓ 好的做法：根据数据大小选择合适的类型
x8 := uint8(0xFF)
bits.OnesCount8(x8)

x64 := uint64(0xFFFFFFFFFFFFFFFF)
bits.OnesCount64(x64)

2. 利用常数时间特性

// ✓ 好的做法：用于安全敏感场景
// bits 函数执行时间不依赖于输入值
result := bits.OnesCount(secretData)

3. 多精度算术

// ✓ 好的做法：使用 Add64/Mul64 实现大数运算
hi, lo := bits.Mul64(a, b)
// 实现 128 位算术

4. 位图应用

// ✓ 好的做法：使用 OnesCount 和 TrailingZeros 优化位图
count := bits.OnesCount64(bitmap)
firstSet := bits.TrailingZeros64(bitmap)

十六、与其他包配合

1. 与 encoding/binary 配合

import (
    "encoding/binary"
    "math/bits"
)

// 字节序转换
x := uint32(0x12345678)
reversed := bits.ReverseBytes32(x)
bytes := make([]byte, 4)
binary.LittleEndian.PutUint32(bytes, reversed)

2. 与 math 包配合

import (
    "math"
    "math/bits"
)

// 检查溢出
sum, carry := bits.Add64(a, b, 0)
if carry != 0 {
    // 处理溢出
    _ = math.MaxUint64
}

十七、快速参考

常量

算术运算

位计数

位变换

类型后缀

所有函数都有针对特定类型的版本：

• 无后缀：uint
• 8：uint8
• 16：uint16
• 32：uint32
• 64：uint64

十八、注意事项

1. 仅适用于无符号整数

// ✗ 错误：不能用于有符号整数
var x int = -5
bits.OnesCount(x) // 编译错误

// ✓ 正确：转换为无符号
bits.OnesCount(uint(x))

2. 除零检查

// Div、Rem 等函数在 y == 0 时会 panic
if y != 0 {
    quo, rem := bits.Div(hi, lo, y)
}

3. 进位/借位必须是 0 或 1

// Add、Sub 的 carry/borrow 必须是 0 或 1
sum, _ := bits.Add(x, y, 0) // ✓
sum, _ = bits.Add(x, y, 1)  // ✓
sum, _ = bits.Add(x, y, 2)  // ✗ 未定义行为

4. 性能优势

• bits 包函数通常被编译器优化为 CPU 指令
• 比手动位操作更快
• 常数时间执行，适合安全敏感场景

最后更新: 2026-04-05
Go 版本: Go 1.9+
包文档: https://pkg.go.dev/math/bits