Bit manipulation guide · 6/6

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 x & (1 == 0). Always parenthesize bitwise expressions.
Overflow: 1 << 31 is negative in Java and JavaScript, and 1 << 40 overflows int in C++. Build wide masks with 1L << i (Java), 1ULL << i (C++) or 1n << 40n (JavaScript BigInt).
Shift counts: Java and JavaScript use only the low 5 bits of a 32-bit shift count, so 1 << 32 is 1. In C++ it is undefined behavior.
Right shifts: in Java and JavaScript >> keeps the sign and >>> fills with zeros. C++ shifts unsigned types logically, and since C++20 right-shifting a negative signed value is defined as arithmetic.
Python negatives: they behave as if they had infinitely many leading 1s, so bin(-5) is -0b101. To mimic 32-bit results, truncate with & 0xFFFFFFFF.

def to_int32(x: int) -> int:
    x &= 0xFFFFFFFF
    return x - (1 << 32) if x & 0x80000000 else x


print(to_int32(1 << 31))    # -2147483648, like 1 << 31 in Java or JS
print(-1 & 0xFFFFFFFF)      # 4294967295, like -1 >>> 0 in JS
print(to_int32(0xDEADBEEF)) # -559038737

The XOR swap (a ^= b; b ^= a; a ^= b) is no faster with modern compilers and zeroes the value if both names refer to the same location, so avoid it. Wrap bit tricks in named constants and small functions so readers can follow them.

Summary

Bit manipulation powers flags, permissions, network addresses, hash tables and bitmap indexes: anywhere many booleans must be handled quickly and compactly. Mind the differences in precedence, integer width and shift rules between languages, and you can write short, fast code safely.