进制与位运算：二进制魔法

进制转换：多项式换底

任何进制表示都是同一个数的不同基底多项式展开。十进制 42 = 4×10¹ + 2×10⁰，二进制 101010 = 1×2⁵ + 0×2⁴ + 1×2³ + 0×2² + 1×2¹ + 0×2⁰。转换本质是换基底，算法是短除法（十→二）和累加（二→十）。

package main

import "fmt"

// 十进制转任意进制（不用标准库）
func toBase(n, base int) string {
    if n == 0 {
        return "0"
    }
    digits := "0123456789ABCDEF"
    result := []
byte{}
    for n > 0 {
        result = append([]byte{digits[n%base]}, result...)
        n /= base
    }
    return string(result)
}

// 任意进制转十进制
func fromBase(s string, base int) int {
    result := 0
    for _, ch := range s {
        d := int(ch - '0')
        if ch >= 'A' {
            d = int(ch-'A') + 10
        }
        result = result*base + d
    }
    return result
}

func main() {
    fmt.Println(toBase(42, 2))   // 101010
    fmt.Println(toBase(255, 16)) // FF
    fmt.Println(fromBase("101010", 2))  // 42
    fmt.Printf("%b %o %x\n", 42, 42, 42) // Go 内置：101010 52 2a
}

位运算六式

package main

import "fmt"

func main() {
    // 快速乘除
    x := 100
    fmt.Println(x << 3)  // x * 8 = 800
    fmt.Println(x >> 2)  // x / 4 = 25

    // 判断奇偶（比 % 快）
    for _, n := range []int{3, 4, 7, 8} {
        fmt.Printf("%d 是%s\n", n, map[bool]string{true: "奇数", false: "偶数"}[n&1 == 1])
    }

    // 不用临时变量交换
    a, b := 0xAA, 0xBB
    a ^= b; b ^= a; a ^= b
    fmt.Printf("a=%X b=%X\n", a, b)  // a=BB b=AA

    // 取最低位的 1
    n := 0b10110100
    lowestBit := n & (-n)  // 0b00000100
    fmt.Printf("%08b\n", lowestBit)

    // 消去最低位的 1（Brian Kernighan trick）
    fmt.Printf("%08b\n", n & (n-1))  // 0b10110000
}

位掩码：用整数表达集合

一个 uint64 可以表示 64 个布尔值的集合，集合操作全部是位运算，时间复杂度 O(1)。这是权限系统、特性开关、状态机的标准实现方式。

package main

import "fmt"

// 权限系统：用位掩码
const (
    PermRead    = 1 << iota  // 0001
    PermWrite                // 0010
    PermExecute              // 0100
    PermAdmin                // 1000
)

func hasPermission(userPerm, required uint) bool {
    return userPerm&required == required
}

func main() {
    // 普通用户：读+写
    user := uint(PermRead | PermWrite)
    fmt.Printf("用户权限: %04b\n", user)

    // 检查权限
    fmt.Println(hasPermission(user, PermRead))    // true
    fmt.Println(hasPermission(user, PermAdmin))   // false

    // 添加权限
    user |= PermExecute
    fmt.Printf("添加执行后: %04b\n", user)  // 0111

    // 移除权限
    user &^= PermWrite  // 位清除（AND NOT）
    fmt.Printf("移除写后: %04b\n", user)    // 0101
}

Brian Kernighan 数 1 的个数

package main

import (
    "fmt"
    "math/bits"
)

// 手写：O(k) k 是 1 的个数
func countOnes(n int) int {
    count := 0
    for n != 0 {
        n &= n - 1  // 消去最低位的 1
        count++
    }
    return count
}

func main() {
    fmt.Println(countOnes(0b10110100))  // 4
    fmt.Println(bits.OnesCount(0b10110100)) // 4（标准库，编译为单条 POPCNT 指令）

    // 判断 2 的幂次
    isPowerOf2 := func(n int) bool { return n > 0 && n&(n-1) == 0 }
    fmt.Println(isPowerOf2(16))  // true
    fmt.Println(isPowerOf2(18))  // false
}

位运算是计算机最原始的语言，掌握它，你就能和 CPU 直接对话。

— The Art of Computer Programming