Real-World Use

Bit manipulation is not just for puzzles. File permissions, network addresses, hash tables, database indexes and game engines all rely on it wherever speed and memory matter. This chapter surveys real uses, lists language-specific pitfalls and points to further reading.

Flags and permissions

The most common use is packing several on/off options into one integer. Unix permission 755 is nine bits written in octal: rwx for owner, group and others. Python's enum.Flag, C#'s [Flags] enums and Java's EnumSet all use bits underneath.

import stat
from enum import Flag, auto

mode = 0o754                                   # rwxr-xr--
print(bool(mode & stat.S_IXUSR))               # True: owner may execute
print(bool(mode & stat.S_IWGRP))               # False: group may not write
print(stat.filemode(stat.S_IFREG | mode))      # -rwxr-xr--


class Perm(Flag):
    READ = auto()
    WRITE = auto()
    EXECUTE = auto()


user = Perm.READ | Perm.WRITE
print(Perm.WRITE in user, Perm.EXECUTE in user)  # True False
user &= ~Perm.WRITE
print(user)                                      # Perm.READ

Network addresses

An IPv4 address is a 32-bit integer; AND it with the subnet mask to get the network address. Routers and firewalls do exactly this for every packet.

import ipaddress

ip = int(ipaddress.IPv4Address("192.168.10.77"))
prefix = 24
mask = (0xFFFFFFFF << (32 - prefix)) & 0xFFFFFFFF
print(ipaddress.IPv4Address(ip & mask))                  # 192.168.10.0
print(ipaddress.ip_interface("192.168.10.77/24").network)  # 192.168.10.0/24

More examples

• Hash tables: Java's HashMap keeps its capacity a power of two and picks a bucket with (n - 1) & hash, which is cheaper than a modulo.
• Bitsets and bitmap indexes: search engines and analytical databases store "does this row match" as one bit and combine filters with AND and OR. Roaring Bitmaps are used in Lucene, Apache Druid and Apache Spark, among others.
• Bloom filters: set the bits at several hash positions, then answer "maybe present" or "definitely absent" by checking them.
• Redis: SETBIT, GETBIT and BITCOUNT store huge numbers of booleans, such as daily active users, in little memory.
• Chess bitboards: 64 squares fit in a 64-bit integer, so move generation becomes shifts and ANDs.
• Fenwick trees: i & -i jumps to the next range.
• Graphics: RGBA colors pack four 8-bit channels into a 32-bit integer, unpacked with shifts and masks.

Pitfalls by language

• Precedence: in C, C++, Java and JavaScript, == binds tighter than &, so x & 1 == 0 means . Always parenthesize bitwise expressions.