Bit Operations in Practice: From Bitmap Indexes to High-Performance Permission Systems

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// Set bit n to 1
x |= (1 << n)

// Clear bit n
x &= ^(1 << n)

// Toggle bit n
x ^= (1 << n)

// Check bit n
(x >> n) & 1

// Get lowest set bit
x & (-x)

// Clear lowest set bit
x & (x - 1)

1
2
3
4
5
6
7
8
9

-rwxr-xr--  1 user group  4096 Dec 10 10:00 file.txt
 ^^^
 421 (owner: read + write + execute = 7)
    ^^^
    421 (group: read + execute = 5)
       ^^^
       421 (others: read = 4)

# Permission value: 754

 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

type Permission uint32

const (
    PermRead    Permission = 1 << 0  // 001 = 1
    PermWrite   Permission = 1 << 1  // 010 = 2
    PermExecute Permission = 1 << 2  // 100 = 4
)

// Check permission
func (p Permission) Has(perm Permission) bool {
    return p&perm == perm
}

// Grant permission
func (p *Permission) Grant(perm Permission) {
    *p |= perm
}

// Revoke permission
func (p *Permission) Revoke(perm Permission) {
    *p &= ^perm
}

// Usage example
func main() {
    var perm Permission = PermRead | PermWrite  // 011 = 3
    
    fmt.Println(perm.Has(PermRead))     // true
    fmt.Println(perm.Has(PermExecute))  // false
    
    perm.Grant(PermExecute)
    fmt.Printf("%03b\n", perm)  // 111
    
    perm.Revoke(PermWrite)
    fmt.Printf("%03b\n", perm)  // 101
}

 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

const (
    PermViewDashboard   uint64 = 1 << 0
    PermEditProfile     uint64 = 1 << 1
    PermCreateProject   uint64 = 1 << 2
    PermDeleteProject   uint64 = 1 << 3
    PermInviteUser      uint64 = 1 << 4
    PermRemoveUser      uint64 = 1 << 5
    PermManageBilling   uint64 = 1 << 6
    PermAccessAdmin     uint64 = 1 << 7
    // ... up to 64 permissions
)

// Predefined roles
const (
    RoleViewer uint64 = PermViewDashboard
    
    RoleEditor uint64 = PermViewDashboard | 
                        PermEditProfile | 
                        PermCreateProject
    
    RoleAdmin uint64 = PermViewDashboard | 
                       PermEditProfile | 
                       PermCreateProject | 
                       PermDeleteProject |
                       PermInviteUser | 
                       PermRemoveUser
    
    RoleOwner uint64 = 0xFFFFFFFFFFFFFFFF  // All permissions
)

 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

type User struct {
    ID          int64
    Permissions uint64  // Only 8 bytes stores all permissions!
}

// O(1) permission check
func (u *User) Can(perm uint64) bool {
    return u.Permissions&perm == perm
}

// Check multiple permissions (all must match)
func (u *User) CanAll(perms ...uint64) bool {
    var required uint64
    for _, p := range perms {
        required |= p
    }
    return u.Permissions&required == required
}

// Check multiple permissions (any matches)
func (u *User) CanAny(perms ...uint64) bool {
    var required uint64
    for _, p := range perms {
        required |= p
    }
    return u.Permissions&required != 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

-- Query user permissions
SELECT p.name 
FROM user_roles ur
JOIN role_permissions rp ON ur.role_id = rp.role_id
JOIN permissions p ON rp.permission_id = p.id
WHERE ur.user_id = ?

-- Check permission
SELECT COUNT(*) 
FROM user_roles ur
JOIN role_permissions rp ON ur.role_id = rp.role_id
WHERE ur.user_id = ? AND rp.permission_id = ?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// Save to database
func (u *User) Save(db *sql.DB) error {
    _, err := db.Exec(
        "UPDATE users SET permissions = ? WHERE id = ?",
        u.Permissions,  // Store uint64 directly
        u.ID,
    )
    return err
}

// Load from database
func LoadUser(db *sql.DB, id int64) (*User, error) {
    var u User
    err := db.QueryRow(
        "SELECT id, permissions FROM users WHERE id = ?",
        id,
    ).Scan(&u.ID, &u.Permissions)
    return &u, err
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// User tags (up to 64)
const (
    TagPremium      uint64 = 1 << 0
    TagVerified     uint64 = 1 << 1
    TagNewUser      uint64 = 1 << 2
    TagHighValue    uint64 = 1 << 3
    TagChurningRisk uint64 = 1 << 4
    // ...
)

type UserIndex struct {
    // Each tag has a bitmap
    // bitmap[i] bit j means user j has tag i
    bitmaps [64][]uint64
    userCount int
}

 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

// Find all "Premium AND Verified AND NOT ChurningRisk" users
func (idx *UserIndex) Query(must, mustNot uint64) []int {
    var result []int
    
    // Calculate match for each block
    blocks := (idx.userCount + 63) / 64
    for b := 0; b < blocks; b++ {
        var match uint64 = 0xFFFFFFFFFFFFFFFF
        
        // AND conditions
        for i := 0; i < 64; i++ {
            if must&(1<<i) != 0 {
                match &= idx.bitmaps[i][b]
            }
        }
        
        // NOT conditions
        for i := 0; i < 64; i++ {
            if mustNot&(1<<i) != 0 {
                match &= ^idx.bitmaps[i][b]
            }
        }
        
        // Extract matching user IDs
        for match != 0 {
            pos := bits.TrailingZeros64(match)
            result = append(result, b*64+pos)
            match &= match - 1  // Clear lowest set bit
        }
    }
    
    return result
}

 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

type BloomFilter struct {
    bits    []uint64
    numHash int
}

func (bf *BloomFilter) Add(item string) {
    for i := 0; i < bf.numHash; i++ {
        hash := bf.hash(item, i)
        idx := hash / 64
        bit := hash % 64
        bf.bits[idx] |= 1 << bit
    }
}

func (bf *BloomFilter) MayContain(item string) bool {
    for i := 0; i < bf.numHash; i++ {
        hash := bf.hash(item, i)
        idx := hash / 64
        bit := hash % 64
        if bf.bits[idx]&(1<<bit) == 0 {
            return false  // Definitely doesn't exist
        }
    }
    return true  // Might exist
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

type LargePermission struct {
    bits []uint64
}

func (p *LargePermission) Set(n int) {
    idx := n / 64
    bit := n % 64
    // Dynamic expansion
    for len(p.bits) <= idx {
        p.bits = append(p.bits, 0)
    }
    p.bits[idx] |= 1 << bit
}

func (p *LargePermission) Has(n int) bool {
    idx := n / 64
    bit := n % 64
    if idx >= len(p.bits) {
        return false
    }
    return p.bits[idx]&(1<<bit) != 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import "sync/atomic"

type AtomicPermission struct {
    bits uint64
}

func (p *AtomicPermission) Grant(perm uint64) {
    for {
        old := atomic.LoadUint64(&p.bits)
        new := old | perm
        if atomic.CompareAndSwapUint64(&p.bits, old, new) {
            return
        }
    }
}

func (p *AtomicPermission) Has(perm uint64) bool {
    return atomic.LoadUint64(&p.bits)&perm == perm
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

type Permission uint64

func (p Permission) MarshalJSON() ([]byte, error) {
    // Convert to permission name list for readability
    names := []string{}
    if p&PermRead != 0 {
        names = append(names, "read")
    }
    if p&PermWrite != 0 {
        names = append(names, "write")
    }
    // ...
    return json.Marshal(names)
}