Bit operations: from beginner to advanced¶

Bit operations are how systems software talks to itself when it cannot afford another byte, another instruction, or another allocation. File permissions, syscall flags, network headers, hashing, compression, cryptography, scheduling priorities, color blending, feature flags, garbage-collector mark bits, CPU instruction encodings - they are all built on the same six operators you can learn in fifteen minutes.

This page walks the whole arc: what a bit is, the six operators, the patterns engineers use them for, real-world places they appear in code you already use, and a small collection of classic tricks worth recognizing on sight. Every section runs in Go (any version), but the operators behave identically in C, Rust, Python, Java, and JavaScript - bits do not care about your language.

1. Why bits matter¶

A modern computer ultimately stores everything as bits. The languages and abstractions you write in - integers, floats, strings, structs, slices - are conventions layered on top of those bits. Most of the time you can ignore the underlying representation; the conventions are good enough. But three situations force you back down:

• You need to be compact. A network packet header has 8 bits to describe a TCP flag set, not 8 booleans worth of memory. A Linux file mode is one integer that encodes nine permission bits and several special bits in a single 16-bit field. A Bloom filter compresses a million booleans into a few kilobytes of bits.
• You need to be fast. A CPU executes a bit-shift in one cycle. The equivalent multiplication or division takes more. Aligning a pointer, hashing a value, computing a checksum, blending two RGBA pixels - all are dominated by bitwise instructions in production code.
• You are talking to hardware or a protocol that was designed before abstractions existed. TCP, UDP, IP, USB, PCIe, the Linux syscall ABI, every file format from PNG to JPEG to MP3 - they are bit layouts. You read them by reaching for bit operators.

If you only ever write business-logic software you can get away without ever seeing a bit operator. But the moment you read a syscall man page, debug a network capture, look at a Kubernetes pod's SELinux context, or write anything that touches a kernel interface, the operators show up. Spend the fifteen minutes now.

2. Beginner: bits, bytes, binary, hexadecimal¶

A bit is a single binary digit - one of 0 or 1. A byte is eight bits. A 32-bit integer is four bytes (32 bits). A 64-bit integer is eight bytes (64 bits).

When we write a number like 13, we are writing it in decimal (base 10). The same number can be written in:

• Binary (base 2): 1101. Reading right-to-left, the bits are worth 1, 2, 4, 8. Bits set: 1, 4, 8. Sum: 13.
• Hexadecimal (base 16): D. One hex digit holds four bits exactly, which is why hex is everywhere in systems code - one hex digit per nibble, two hex digits per byte. The hex digits 0-9 mean what they look like; A-F mean 10-15.

Go (and most languages) lets you write integers in any of these forms:

package main

import "fmt"

func main() {
    a := 13       // decimal
    b := 0b1101   // binary  (Go 1.13+)
    c := 0xD      // hexadecimal
    fmt.Println(a, b, c)  // 13 13 13 - the same number, three notations
}

Why hex shows up everywhere. A byte is 8 bits = 2 hex digits = one pair like 0xFF. A 32-bit address is 8 hex digits like 0xCAFEBABE. Looking at memory in hex is a one-to-one mapping with the underlying bits; looking at it in decimal hides the boundaries between bytes.

Try it:

1. Write 42 in binary on paper (answer: 101010). Confirm with fmt.Printf("%b\n", 42).

2. Write 255 in hex on paper (answer: FF). Confirm with fmt.Printf("%x\n", 255).

3. Run fmt.Printf("%08b\n", 13). The %08b means "binary, padded to 8 digits with zeros." Useful for reading flag bytes.

3. Beginner: the six operators¶

Every bit-handling skill in the rest of this page is built from six operators. Memorize the symbols, memorize what each one does to a single pair of bits, and the patterns follow.

3.1 AND - &¶

Bit-by-bit AND. The result bit is 1 only if both input bits are 1.

  1101
& 1011
------
  1001

fmt.Printf("%04b\n", 0b1101 & 0b1011)   // 1001

The dominant use: isolate (extract) the bits you care about by ANDing with a mask. Want only the low 4 bits of a number? n & 0x0F. Want bit 3 alone? n & 0b1000.

3.2 OR - |¶

Bit-by-bit OR. The result bit is 1 if either input bit is 1.

  1100
| 1010
------
  1110

fmt.Printf("%04b\n", 0b1100 | 0b1010)   // 1110

The dominant use: turn bits on in a flag field. To set bit 2 of n, write n = n | 0b100. Bits that were already on stay on; bit 2 becomes on no matter what it was.

3.3 XOR - ^¶

Bit-by-bit exclusive-or. The result bit is 1 only if the inputs differ.

  1100
^ 1010
------
  0110

fmt.Printf("%04b\n", 0b1100 ^ 0b1010)   // 0110

XOR has two superpowers:

• It is reversible. a ^ b ^ b == a. XOR with the same value twice undoes itself. This is the basis of trivial stream ciphers, CRCs, and the "swap without a temp variable" trick later in this page.
• It detects difference. A bit is 1 in the result exactly when the two inputs differ at that position. So a ^ b == 0 if and only if a == b. Hash tables, error detection, and parity bits all lean on this.

A subtle but important point in Go: ^ is also the unary operator for bitwise NOT (see §3.5). The same symbol does both depending on whether it has one operand or two.

3.4 Left shift - <<¶

Shift bits to the left by n positions; fill new low bits with zeros.

  0000_0011 << 2
= 0000_1100

That is, 3 << 2 = 12. Each shift left by one position is the same as multiplying by 2; shifting by n multiplies by 2^n. So 1 << 10 = 1024, 1 << 20 = 1,048,576, 1 << 30 = 1,073,741,824 - this is exactly the trick the iota example in the Go path uses to define KB, MB, GB.

fmt.Println(1 << 10)   // 1024
fmt.Println(1 << 20)   // 1048576
fmt.Println(1 << 30)   // 1073741824

Shifting by the width of the type (32 or 64) is undefined behavior in C and a runtime panic in Go for shifts that exceed the type width - use it for small n.

3.5 Right shift - >>¶

Shift bits to the right by n positions; the high bits get filled with zeros (for unsigned types) or with copies of the sign bit (for signed types). Each shift right by one position is the same as integer-dividing by 2.

  0000_1100 >> 2
= 0000_0011

12 >> 2 = 3. The low bits "fall off" the end; they are lost.

fmt.Println(12 >> 2)   // 3
fmt.Println(1 << 30 >> 20)   // 1024  (shifted up then down)

A right shift is dramatically faster than division on most CPUs. Compilers will already do this for you when dividing by a constant power of two, but you will see explicit >> in performance-critical code (hash table sizing, memory allocators, kernel code) because it makes the intent clearer.

3.6 NOT - ^ (unary)¶

Flip every bit. Where there was a 0, write a 1; where there was a 1, write a 0.

  0000_1010
~ (unary)
= 1111_0101

In Go, the unary form of ^ is the bitwise NOT. (In C, Java, Python, Rust, and most other languages it is ~; Go reuses ^.)

var n uint8 = 0b00001010
fmt.Printf("%08b\n", ^n)   // 11110101

Note that flipping all bits of an unsigned 8-bit 10 gives you 245, not -10. Whether NOT gives you a negative number depends on whether the type is signed and on the bit width. Stick to unsigned types when learning bit operations; the rules are simpler.

The dominant use: build a mask of "everything except these bits." If mask is the bits you want to clear, ^mask is the bits you want to keep, and n & ^mask clears them. We will use this pattern constantly in §5.

3.7 A summary table¶

These six are the whole alphabet. Everything that follows is a phrase.

4. Intermediate: bit flags (the most useful pattern)¶

Imagine you are designing a function OpenFile(path string, options ???) and the options can be any combination of:

• read
• write
• append
• create if missing
• truncate to zero length on open
• sync writes to disk

You could pass six booleans. Almost no real API does this. Instead you pack the six options into the bits of a single integer:

const (
    Read     = 1 << 0   // 0b000001 = 1
    Write    = 1 << 1   // 0b000010 = 2
    Append   = 1 << 2   // 0b000100 = 4
    Create   = 1 << 3   // 0b001000 = 8
    Truncate = 1 << 4   // 0b010000 = 16
    Sync     = 1 << 5   // 0b100000 = 32
)

Each constant is a different bit position. A caller passes a combination by ORing them together:

opts := Read | Write | Create     // 0b001011 = 11

Inside the function, you check whether a flag is set by ANDing with the corresponding mask and testing for nonzero:

if opts & Write != 0 {
    // caller asked for write
}

That is the entire pattern, and you will see it everywhere:

• The Linux open(2) syscall: O_RDONLY, O_WRONLY, O_RDWR, O_APPEND, O_CREAT, O_TRUNC, O_SYNC - read /usr/include/bits/fcntl-linux.h and they are exactly 1 << n constants.
• Go's os.OpenFile(name string, flag int, perm os.FileMode) - the flag argument is one of these OR'd-together integers.
• HTTP/2 frame flags: END_STREAM, END_HEADERS, PADDED, PRIORITY are bits in a single byte.
• TCP flags: URG, ACK, PSH, RST, SYN, FIN are six bits in a single byte of the TCP header.
• Kubernetes scheduling: pod tolerations and node taints use bit fields internally for fast matching.

Try it.

1. Define Read, Write, Append, Create flags.

2. Build a String() method on a flag type that prints which bits are set ("Read|Create" for Read | Create).

3. Test that opts & Write == 0 correctly reports "write is off."

5. Intermediate: the four canonical mask operations¶

Given a flag value n and a single-bit mask m, there are four things you ever want to do.

5.1 Set a bit¶

Turn on the bit corresponding to mask m, leaving all other bits alone.

n = n | m

If the bit was already on, it stays on. If it was off, it becomes on. Other bits unchanged. This is "OR sets."

5.2 Clear a bit¶

Turn off the bit corresponding to mask m, leaving all other bits alone.

n = n &^ m   // Go's "and not" operator; equivalent to n = n & ^m

Go has a dedicated &^ (AND NOT) operator that does both steps at once. In C and Rust you would write n & ~m. Read it as "n with m's bits removed."

The construction in plain operators: ^m is "the complement of m" - a mask where every bit is on except those of m. ANDing with that complement keeps every bit of n except the ones in m. This is "AND NOT clears."

5.3 Toggle a bit¶

Flip the bit corresponding to mask m: on becomes off, off becomes on. Other bits unchanged.

n = n ^ m

This is the cleanest XOR use you will encounter. If the bit was 0, XOR with 1 makes it 1. If it was 1, XOR with 1 makes it 0. Other bit positions are XORed with 0, which leaves them alone.

5.4 Test a bit¶

Is the bit set? Returns 0 (no) or nonzero (yes).

if n & m != 0 {
    // bit is set
}

You can also normalize to true/false with (n & m) != 0. Some style guides prefer the explicit comparison; both are correct.

5.5 Putting them together¶

const (
    Read   = 1 << 0
    Write  = 1 << 1
    Append = 1 << 2
)

var opts uint8

opts = opts | Read              // set Read
opts = opts | Write             // set Write
fmt.Printf("%03b\n", opts)      // 011

opts = opts ^ Append            // toggle Append (turns on; was off)
fmt.Printf("%03b\n", opts)      // 111

opts = opts &^ Write            // clear Write
fmt.Printf("%03b\n", opts)      // 101

fmt.Println(opts & Read != 0)   // true
fmt.Println(opts & Write != 0)  // false

These four operations are 80% of all bit code you will ever write or read.

6. Intermediate: packing fields into one integer¶

Sometimes you want more than a yes/no flag - you want a small number packed into a few bits. Network protocols and file formats do this constantly because every saved bit is real money at protocol scale.

Suppose you have a 16-bit field and you want to pack:

• 4 bits of version (0-15)
• 8 bits of type (0-255)
• 4 bits of length (0-15)

 bit:  15 14 13 12 | 11 10 9 8 7 6 5 4 | 3 2 1 0
       [version  ] | [    type        ] | [ length ]

Packing (build the integer from the three fields):

func pack(version, typ, length uint16) uint16 {
    return (version & 0xF) << 12 |
           (typ     & 0xFF) << 4 |
           (length  & 0xF)
}

Each field is ANDed with a mask of its own width to make sure no stray high bits leak into a neighboring field, then shifted into position, then OR'd together. This is the canonical packing pattern.

Unpacking (pull the three fields back out of the integer):

func unpack(packed uint16) (version, typ, length uint16) {
    version = (packed >> 12) & 0xF
    typ     = (packed >> 4)  & 0xFF
    length  = packed         & 0xF
    return
}

Each field is shifted down so its low bit lives at position 0, then ANDed with a mask of its width to discard anything above. Same pattern in reverse.

This is exactly how an IPv4 header is laid out (version, IHL, TOS, total length, flags, fragment offset...), how a UTF-8 byte is decoded, how the Linux mode_t file permission word is structured, and how Kubernetes' garbage collector pacing bits live inside a single status word.

7. Intermediate: powers of two and alignment¶

Two facts make powers of two everywhere in systems code:

• x & (x-1) clears the lowest set bit of x. So x & (x-1) == 0 if and only if x is a power of two (or zero). This is the standard "is it a power of two" check.
• For a power of two p, n & (p-1) is the same as n % p, but much faster. Modulo by a power-of-two can always be replaced by an AND with p-1. This is why hash tables size themselves to powers of two and CPU pages are 4096 = 2^12 bytes - the address arithmetic is a free & instead of a division.

func isPowerOfTwo(x uint32) bool {
    return x != 0 && x & (x-1) == 0
}

func alignUp(n, align uint32) uint32 {
    // Round n up to the next multiple of align, which MUST be a power of two.
    return (n + align - 1) & ^(align - 1)
}

fmt.Println(isPowerOfTwo(1024))   // true
fmt.Println(isPowerOfTwo(1000))   // false
fmt.Println(alignUp(13, 8))       // 16
fmt.Println(alignUp(16, 8))       // 16
fmt.Println(alignUp(17, 8))       // 24

alignUp is one of the most used helpers in low-level code: memory allocators, garbage collectors, network protocol parsers, and binary file readers all need to round a position up to the next alignment boundary. The & form runs in a single cycle on every modern CPU; the equivalent ((n + align - 1) / align) * align is two divisions and a multiplication.

  user  group other
   rwx   r-x   r--
   111   101   100   in binary
    7     5     4    in octal

  bit:  7 6 5 4 | 3 2 1 0
        [ver. ] | [IHL  ]

func parseV1(b byte) (version, ihl byte) {
    version = (b >> 4) & 0xF
    ihl     = b & 0xF
    return
}

  bits:  31..24 | 23..16 | 15..8  | 7..0
         red    | green  | blue   | alpha

func popcountSlow(x uint64) int {
    count := 0
    for x != 0 {
        count += int(x & 1)
        x >>= 1
    }
    return count
}

var x int32 = 0b0010_1100
fmt.Printf("%08b\n", x & -x)   // 00000100 - the lowest set bit, alone

func nextPowerOfTwo(x uint32) uint32 {
    if x == 0 {
        return 1
    }
    x--
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    return x + 1
}

a, b := 7, 13
a ^= b
b ^= a
a ^= b
fmt.Println(a, b)   // 13 7

func signExtend(value uint32, bits uint) int32 {
    shift := 32 - bits
    return int32(value << shift) >> shift
}

func reverseBits32(x uint32) uint32 {
    x = (x >> 1)  & 0x55555555 | (x & 0x55555555) << 1
    x = (x >> 2)  & 0x33333333 | (x & 0x33333333) << 2
    x = (x >> 4)  & 0x0F0F0F0F | (x & 0x0F0F0F0F) << 4
    x = (x >> 8)  & 0x00FF00FF | (x & 0x00FF00FF) << 8
    x = (x >> 16)              | (x << 16)
    return x
}

10. Where to go from here¶

You now have:

• The vocabulary (six operators) and the four canonical mask operations.
• The pattern for packing and unpacking fixed-width fields - which is half of all binary protocol code.
• A handful of recognized tricks (popcount, lowest set bit, power-of-two round-up) that show up in real codebases.

Concrete next steps:

• Read a network header parser in your favorite language's standard library. In Go, net/textproto is the wrong choice; look at golang.org/x/net/ipv4 or the gopacket library. Every header field is one of the patterns above.
• Read the Linux /usr/include/bits/fcntl-linux.h to see how O_RDONLY, O_WRONLY, etc. are defined. They are exactly the 1 << n constants from §4.
• Open math/bits in the Go standard library and skim the functions: OnesCount, LeadingZeros, TrailingZeros, RotateLeft, Reverse. Each one is a single CPU instruction on modern hardware; the package is a thin portable wrapper.
• Read Hacker's Delight by Henry S. Warren if you want the deep version. It is the canonical reference for bit tricks; almost every advanced pattern in this section is from there.

Bit operations are not a separate field of programming; they are the spelling of how computers actually represent data. Once you can read them on sight, large swaths of systems software stop being opaque.