Bitwise operators and number bases

Why this matters

Underneath every value is a pattern of bits, and some jobs work directly on those bits: Unix file permissions (chmod 755), network masks (255.255.255.0), colors (#ff8800), hardware registers, compact sets of on/off options ("flags"), checksums and hashing. You will meet hexadecimal in error messages, memory addresses and byte dumps constantly. This lesson teaches you to read binary, octal and hex fluently and to use Python's bitwise operators to test, set and clear individual bits.

Positional number systems

The number 254 in decimal means 2 hundreds, 5 tens and 4 ones: each position is worth 10 times the one to its right. Other bases work the same way with a different multiplier.

decimal 13   = 1*10 + 3*1
binary  1101 = 1*8 + 1*4 + 0*2 + 1*1             = 13
octal   15   = 1*8 + 5*1                         = 13
hex     d    = 13                                (digits 0-9, then a=10 ... f=15)

• Binary (base 2) is how the hardware stores everything. Each digit is a bit; 8 bits make a byte (values 0-255).
• Hexadecimal (base 16) is a compact way to write binary: each hex digit is exactly 4 bits, so a byte is always two hex digits (0x00 to 0xff).
• Octal (base 8): each digit is exactly 3 bits. It survives mainly in Unix permissions.

binary:  1100 1000      hex digit per 4 bits:  c    8     ->  0xc8
binary:  11 001 000     octal digit per 3 bits: 3  1   0   ->  0o310

Writing and printing other bases in Python

Integer literals can be written in any of these bases using a prefix. They all produce the same kind of int object; the base is only about spelling:

print(0b11001000)   # binary literal
print(0o310)        # octal literal
print(0xc8)         # hex literal (case-insensitive: 0xC8)
print(0xc8 == 200)

200
200
200
True

To go the other way, from int to text in a base, use bin, oct and hex, which return strings with the prefix. And int(text, base) (from the conversion lesson) parses text:

n = 200
print(bin(n), oct(n), hex(n))
print(int("c8", 16), int("11001000", 2))

0b11001000 0o310 0xc8
200 200

format(n, "b"), format(n, "x") and f-strings (f"{n:08b}") give the digits without prefix and with padding; the strings module covers formatting.

The bitwise operators

These operators work on the binary representation of ints, bit by bit:

operator   name          rule for each bit            example with 12 (1100) and 10 (1010)
a & b      AND           1 if both bits are 1         1000 = 8
a | b      OR            1 if either bit is 1         1110 = 14
a ^ b      XOR           1 if exactly one bit is 1    0110 = 6
~a         NOT           flips every bit              ~12 = -13
a << n     left shift    moves bits n places left     12 << 1 = 24
a >> n     right shift   moves bits n places right    12 >> 2 = 3

a, b = 0b1100, 0b1010
print(bin(a & b), bin(a | b), bin(a ^ b))
print(1 << 10)      # 2 ** 10
print(200 >> 4)     # 200 // 16

0b1000 0b1110 0b110
1024
12

Shifting left by n multiplies by 2n, and shifting right by n is floor division by 2n. Python ints never overflow, so 1 << 100 is simply a large exact number.

NOT and negative numbers

Hardware stores negative integers in two's complement: flip all bits and add one. Python ints act as if they had infinitely many bits in two's complement, so negative numbers have infinitely many leading 1s. That makes ~x always equal -x - 1:

print(~5, ~0, ~-1)
print(bin(-5))
print(-5 & 0xFF)    # view -5 as an 8-bit byte

-6 -1 0
-0b101
251

bin(-5) shows a minus sign and the magnitude, not the bit pattern. To see the fixed-width pattern you would get in C, mask with & 0xFF (8 bits), & 0xFFFF (16) and so on: 251 is 11111011, the 8-bit two's complement of -5.

Bit flags

A classic use: storing several yes/no options in one integer, one bit each.

READ = 0b100     # 4
WRITE = 0b010    # 2
EXEC = 0b001     # 1

perms = READ | WRITE        # set two flags
print(bin(perms))
print(perms & WRITE != 0)   # test a flag
print(perms & EXEC != 0)
perms |= EXEC               # set a flag
perms &= ~WRITE             # clear a flag
print(bin(perms))
perms ^= READ               # toggle a flag
print(bin(perms))

0b110
True
False
0b101
0b1

The idioms to remember:

• set a bit: x |= FLAG
• clear a bit: x &= ~FLAG
• toggle a bit: x ^= FLAG
• test a bit: x & FLAG != 0 (or just if x & FLAG:)
• extract a field: (x >> shift) & mask

Unix permissions are exactly this. chmod 754 sets the 9-bit value 0o754: owner rwx (7 = 4+2+1), group r-x (5 = 4+1), others r-- (4). Python's os.stat(path).st_mode & 0o777 gives these bits for a real file, and the stat module names the constants (stat.S_IROTH is 0o004). The standard library also offers enum.Flag for named flag sets, which you may meet later.

Precedence of bitwise operators

In Python, from high to low: unary ~, then arithmetic, then shifts << >>, then &, then ^, then |, and only then comparisons. So:

x = 6
print(x & 4 != 0)     # (x & 4) != 0
print(1 << 2 + 1)     # 1 << (2 + 1): + binds more tightly than <<

True
8

This differs from C, where x & 4 != 0 means x & (4 != 0), a famous source of bugs. Even in Python, parentheses make bit expressions much easier to read.

Common mistakes

• ^ for exponent. 2 ^ 10 is 8 (XOR). Power is 2 ** 10.
• Confusing &/| with and/or. and/or work on truthiness and short-circuit; &/| combine bits and always evaluate both sides. True & False happens to work (bools are ints), but 5 and 3 is 3 while 5 & 3 is 1.
• Expecting fixed-width results. ~5 is -6, not 250. Mask with & 0xFF (or the width you need).
• Shift precedence. 1 << n - 1 is 1 << (n - 1), not (1 << n) - 1.
• Octal confusion. A leading zero like 0755 is a SyntaxError in Python 3 ("leading zeros in decimal integer literals are not permitted; use an 0o prefix for octal integers"). Write 0o755.

Recap

• Binary, octal and hex are spellings of the same ints: literals 0b..., 0o..., 0x...; bin, oct, hex to print; int(text, base) to parse.
• One hex digit is 4 bits, one octal digit 3 bits, one byte 8 bits.
• &, |, ^, ~, <<, >> work bit by bit; shifts multiply or floor-divide by powers of two.
• Python ints behave like infinite-width two's complement: ~x == -x - 1; mask to get fixed widths.
• Flags: set |=, clear &= ~, toggle ^=, test &, extract (x >> s) & mask.

Going further: run ls -l and stat -c '%a %A' somefile in a terminal, then decode the octal mode by hand. Read about int.bit_length() and int.bit_count() (Python 3.10+) in help(int).