Bits, Bytes & Endianness

A computer stores every integer as a row of bits — switches that are either 0 or 1. Bitwise operators work on those individual switches rather than on the number as a whole. To use them you need to read the same number in several bases, so that is where we start.

Place value, and why bases exist

In ordinary decimal, each column is worth ten times the one to its right. The number 237 means 2×100 + 3×10 + 7×1. Nothing about that is fundamental — ten is just how many fingers we have. Change the multiplier and you change the base.

Binary — base 2

Each column is worth twice the one to its right. Python writes binary literals with an 0b prefix:

0b1011

Read it by columns:

  1   0   1   1
  ↓   ↓   ↓   ↓
  8   4   2   1     ← place values

  8 + 0 + 2 + 1  =  11

So 0b1011 and 11 are the same integer written two ways. Python will confirm it:

>>> 0b1011 == 11
True

Octal — base 8

Columns worth 1, 8, 64, 512. Prefix 0o:

0o17

  1   7
  ↓   ↓
  8   1

  1×8 + 7×1  =  15

Octal is mostly a historical curiosity now, with one survivor you use constantly: Unix file permissions. chmod 755 is octal, and each digit is three bits of read/write/execute.

Hexadecimal — base 16

Columns worth 1, 16, 256, 4096. Prefix 0x. Base 16 needs sixteen digit symbols and we only have ten, so the last six are letters:

So:

0xff

  F    F
  ↓    ↓
  16   1

  15×16 + 15×1  =  240 + 15  =  255

0xF = 1111      0xA = 1010      0x3 = 0011
0xFF = 1111 1111   ← one byte, read straight off

Converting between bases in Python

Three built-ins convert from an integer:

>>> bin(11)
'0b1011'
>>> oct(15)
'0o17'
>>> hex(255)
'0xff'

>>> type(bin(11))
<class 'str'>
>>> bin(11) + 1
TypeError: can only concatenate str (not "int") to str

And int() converts the other way, taking the base as its second argument:

>>> int('ff', 16)      # read 'ff' as base 16
255
>>> int('1011', 2)
11
>>> int('17', 8)
15
>>> int('0xff', 16)    # prefix is tolerated
255
>>> int('ff', 0)       # base 0 = infer from prefix; no prefix here, so:
ValueError: invalid literal for int() with base 0: 'ff'

The same digit string means different numbers in different bases, which is the whole point:

>>> int('1010', 2), int('1010', 10), int('1010', 16)
(10, 1010, 4112)

format() — padded binary for reading bits

bin() is awkward when you want to line bits up, because it strips leading zeros and adds a prefix. format() fixes both:

>>> format(11, '08b')
'00001011'

The format spec reads right to left:

  '08b'
   │││
   ││└── b  = render in binary
   │└─── 8  = minimum total width
   └──── 0  = pad with zeros (not spaces)

Compare the three:

>>> format(11, 'b')      # no padding
'1011'
>>> format(11, '8b')     # pad to 8 with SPACES
'    1011'
>>> format(11, '08b')    # pad to 8 with ZEROS
'00001011'
>>> format(11, '016b')   # 16-bit view
'0000000000001011'

This is the tool you will reach for every time you want to see what an operator did. Keep it nearby.

The six bitwise operators

For every example below, these two numbers:

n = 11 = 1011
m =  5 = 0101

The operators compare the two rows column by column, independently. No column affects any other — that is what makes them different from arithmetic, where carries propagate.

& — AND

A column is 1 only when both bits are 1.

    1011   (11)
 &  0101   (5)
 ────────
    0001   (1)

>>> 11 & 5
1

Use it to ask questions. AND with a mask keeps only the bits you care about and zeroes everything else.

| — OR

A column is 1 when at least one bit is 1.

    1011   (11)
 |  0101   (5)
 ────────
    1111   (15)

>>> 11 | 5
15

Use it to add bits. OR turns bits on and never turns any off.

^ — XOR (exclusive or)

A column is 1 when the two bits differ.

    1011   (11)
 ^  0101   (5)
 ────────
    1110   (14)

>>> 11 ^ 5
14

Use it to flip bits, and to cancel things out. XOR is the operator with real algebra behind it, which we come back to in the next section — it is the engine behind both of today's problems.

~ — NOT

Flips every bit. This is the one that surprises everybody:

>>> ~11
-12

You might have expected 4, reasoning that 1011 inverted is 0100. The answer is −12 because Python integers have no fixed width. There is no 8-bit or 32-bit box for the flipped bits to live in — conceptually the number extends leftwards forever, so inverting it flips infinitely many leading zeros into leading ones, which is how negative numbers are represented.

The identity to remember:

~n  ==  -(n + 1)

>>> ~0, ~5, ~11, ~100
(-1, -6, -12, -101)

Day 02 explains why that identity holds, when we do two's complement properly. For now, treat it as a fact and note the practical consequence: in Python, if you want a bounded NOT you must supply the bound yourself by masking:

>>> ~11 & 0xFF          # NOT within 8 bits
244
>>> format(244, '08b')
'11110100'            # 00001011 inverted, as expected

<< — left shift

Moves every bit left by k places, filling in zeros on the right.

11 = 1011

11 << 1:   1011 → 10110    = 16+4+2   = 22
11 << 2:   1011 → 101100   = 32+8+4   = 44
11 << 3:   1011 → 1011000  = 64+16+8  = 88

Shifting left by one doubles the number, because every bit moves into a column worth twice as much:

n << k  ==  n × 2**k

>>> 11 << 1, 11 << 2, 11 << 3
(22, 44, 88)
>>> 1 << 10            # the idiomatic way to write 1024
1024

1 << k builds a number with a single bit set at position k. That is the most useful shift in practice and you will see it in every idiom below.

>> — right shift

Moves every bit right by k places. Bits that fall off the right-hand end are discarded, which makes this lossy.

11 = 1011

11 >> 1:   1011 → 101    = 4+1  = 5    (the final 1 was dropped)
11 >> 2:   1011 → 10     = 2     = 2
11 >> 3:   1011 → 1      = 1     = 1

For non-negative integers this is floor division by a power of two:

n >> k  ==  n // 2**k      # for n ≥ 0

>>> 20 >> 1, 20 >> 2, 20 >> 3
(10, 5, 2)

>>> -5 >> 1
-3                  # floor(-2.5) = -3, not -2
>>> -1 >> 1
-1                  # and -1 never goes anywhere, however far you shift

Two integer methods worth knowing

.bit_length()

How many binary digits the number needs, ignoring leading zeros and ignoring the sign.

>>> (255).bit_length()
8                  # 255 = 11111111 → eight digits

The pattern is that it ticks up at each power of two:

Useful shortcut: n.bit_length() is floor(log2(n)) + 1 for positive n, but computed exactly, with no floating-point error. Prefer it over math.log2 whenever the answer must be exact.

.bit_count() — population count

How many bits are set to 1. Added in Python 3.10.

>>> (255).bit_count()
8                  # 11111111 — eight ones
>>> (11).bit_count()
3                  # 1011 — three ones
>>> (16).bit_count()
1                  # 10000 — one one
>>> (10).bit_count()
2                  # 1010 — two ones

The traditional name is popcount, and you will see that word everywhere. On older Python, bin(n).count('1') does the same thing far more slowly.

A real use: flags and permissions

This is where bitwise operations actually earn their place in ordinary code. Give each independent boolean its own bit:

READ   = 1   # 001
WRITE  = 2   # 010
DELETE = 4   # 100

Combine with OR:

>>> perms = READ | WRITE
>>> perms
3
>>> format(perms, '03b')
'011'

    001   READ
 |  010   WRITE
 ──────
    011   both, in one integer

Test with AND:

>>> perms & WRITE          #   011 & 010 = 010
2                       # non-zero → yes
>>> perms & DELETE         #   011 & 100 = 000
0                       # zero → no

if perms & WRITE:        # the idiomatic test
    ...

Revoke with AND-NOT, toggle with XOR:

>>> perms & ~WRITE         # clear the WRITE bit
1
>>> perms ^ DELETE         # flip DELETE on (or off, if it were on)
7

Three booleans in one integer, each test a single CPU instruction. This exact pattern is how Unix file modes, TCP header flags, CPU status registers and most permission systems you have used are built.

The same operators in Rust

Rust does the identical bit arithmetic, but forces one thing into the open that Python hides: the width of the integer.

let a: u8  = 0b1011_1010;   // unsigned, 8 bits
let b: i32 = 0xff;         // signed, 32 bits

Reading the type names: u is unsigned (zero and up), i is signed (negatives allowed), and the number is how many bits.

The underscore in 0b1011_1010 is purely cosmetic — Rust lets you put it anywhere in a numeric literal to group digits. 0b1011_1010, 0b10111010 and 186 are the same value. Use it to group bits in fours and hex in bytes:

1_000_000        0xff_ff        0b1010_1010

Operator differences

Note that ! in Rust is both logical not (on bool) and bitwise not (on integers) — the type decides which. Python needs two symbols, not and ~, because an integer is also truthy.

The methods Python does not have

Because Rust knows the width, it can answer questions Python cannot. Using a: u8 = 0b1011_1010 throughout:

// 1 0 1 1 1 0 1 0   ← always exactly 8 bits, because u8

a.count_ones()        // 5  — five bits are set
a.count_zeros()       // 3
a.leading_zeros()     // 0  — the top bit is already 1
a.trailing_zeros()    // 1  — one zero at the bottom end

Change the value and the width still anchors the answer:

let x: u8 = 0b0001_1010;
//          ^^^ three leading zeros
x.leading_zeros()     // 3

let y: u8 = 0b1011_1000;
//                ^^^ three trailing zeros
y.trailing_zeros()    // 3

leading_zeros is impossible in Python because an integer has no declared width — there is no agreed number of leading zeros to count. That is the whole difference between the two languages in one method.

Rotate versus shift

A shift throws bits away. A rotation wraps them around to the other end.

a = 1011_1010

a << 3          // SHIFT: 101 falls off the left and is lost
  1101_0000     // = 208

a.rotate_left(3)  // ROTATE: 101 comes back around on the right
  1101_0101     // = 213

Step through the rotation one place at a time if it helps:

  1011_1010   start
  0111_0101   rotate 1 — the leading 1 reappears at the end
  1110_1010   rotate 2
  1101_0101   rotate 3 ✓

Rotation only makes sense when the width is known, which is why Python has no built-in for it. It matters because cryptography, hashing and checksums are built almost entirely out of rotations and XOR — no bit is ever allowed to be lost, because the operation has to be reversible.

Width is a real constraint

1u64 << 63     // fine — lands on the top bit of 64
1u32 << 31     // fine — lands on the top bit of 32
1u32 << 32     // PANIC in debug: shift amount ≥ width
1u32 << 63     // PANIC — meaningless in a 32-bit value

In Python, 1 << 63 and 1 << 6300 both just work, because the integer grows to fit. In C the same shift is undefined behaviour, which is worse than a panic: the compiler is entitled to assume it never happens and optimise accordingly. Rust's choice to panic loudly in debug and wrap predictably in release is the deliberate middle path.

You now have the operators. This section is the vocabulary built from them — the handful of expressions that appear in real bit-manipulation code, and why each one works rather than just that it does.

The idiom table

Learn these as phrases, not puzzles. i counts from 0 at the rightmost bit.

That (1 << k) - 1 trick is worth its own moment, because it recurs constantly. Subtracting one from a lone bit borrows all the way down and fills everything beneath it:

1 << 4       = 0001_0000  = 16
(1 << 4) - 1 = 0000_1111  = 15     ← exactly four ones

Why n & (n - 1) clears the lowest set bit

Subtracting one flips the lowest 1 to 0 and turns every zero below it into a one. AND that against the original and the lower region cancels completely:

n      = 0010_1100   (44)
n - 1  = 0010_1011   (43)  — lowest 1 cleared, zeros below became ones
         ─────────
n&(n-1)= 0010_1000   (40)  — the lowest set bit is gone, rest untouched

Repeat until zero and you have counted the set bits, visiting each exactly once. This is Brian Kernighan's algorithm:

def popcount(n):
    count = 0
    while n:
        n &= n - 1      # remove the lowest set bit
        count += 1
    return count

The loop runs once per set bit, not once per bit position — which for a sparse value is the difference between one iteration and sixty-four.

Why n & -n isolates the lowest set bit

This looks like nonsense until you know what negation does to the bits. Negating in two's complement means invert every bit, then add one (tomorrow's topic, taken on faith today):

n        = 0010_1000
invert   = 1101_0111
add 1    = 1101_1000   = -n

n        = 0010_1000
-n       = 1101_1000
           ─────────
n & -n   = 0000_1000   ← the lowest set bit, alone

The reason it works is the carry. Adding one after inverting propagates upward through the trailing ones of the inverted value — which were the trailing zeros of the original — and stops at the first position that had a 1. The result:

• Below the lowest set bit: original is all zeros, so the AND is zero.
• At the lowest set bit: both are 1, so it survives.
• Above it: the carry stopped, so those bits are the plain inversion of the original — every column has one 1 and one 0, and the AND kills them all.

It works in Python too, despite Python having no fixed width, because Python integers behave as though two's complement extends infinitely to the left. This expression is the foundation of the Fenwick tree you will meet on day 33.

XOR is the operator with algebra

Four properties. Every XOR trick in existence is a consequence of them:

Commutativity and associativity together mean order does not matter at all. So if you XOR an entire array in which every value appears twice except one, the pairs annihilate each other no matter how far apart they sit, and what remains is the unpaired value:

[4, 1, 2, 1, 2]

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)    ← reorder freely
= 4 ^ 0 ^ 0
= 4

from functools import reduce
from operator import xor
reduce(xor, [4,1,2,1,2])     # 4 — O(n) time, O(1) space

Two more consequences you will use today:

• XOR is its own undo. a ^ k ^ k == a. This is why the simplest (and weakest) ciphers are XOR with a key.
• If a ^ b == t then a ^ t == b. Rearranging works exactly like ordinary algebra. Problem 2 is built entirely on this.

An integer as a set

Once bit i means "element i is present", a single integer is a whole set and the set operations become single instructions:

s = 0                      # empty set
s |= 1 << 3                # add element 3
s |= 1 << 5                # add element 5
if s >> 3 & 1: ...           # membership
s &= ~(1 << 3)             # remove element 3

a | b                     # union
a & b                     # intersection
a & ~b                    # difference
a ^ b                     # symmetric difference
a & b == a                # a is a subset of b
s.bit_count()             # size

This is why competitive code is full of bitmasks, and it is what makes subset dynamic programming tractable at all — day 22.

Enumerating every subset of a mask

One genuinely non-obvious idiom, included because it has a complexity result attached:

sub = mask
while sub:
    process(sub)
    sub = (sub - 1) & mask    # next smaller submask
# the loop exits on 0, so handle the empty submask separately if you need it

Subtracting one borrows through the mask's own bits; ANDing back with the mask discards whatever borrowed outside it. The effect is a clean descending walk through every subset.

The byte is the unit of address

A byte is eight bits and it is the smallest thing in a computer with its own address. Memory is a numbered sequence of bytes; addresses count bytes, never bits.

A word is the processor's natural working width — 64 bits on Apple silicon. Its general-purpose registers are x0 through x30, each 64 bits, and w0–w30 name the lower 32 bits of those same registers rather than separate storage.

The units, since they get used loosely: 4 bits is a nibble (one hex digit), 8 is a byte, and "half word", "word" and "double word" mean different sizes depending on whose manual you are reading — always check.

Endianness — byte order within a value

A 32-bit value occupies four consecutive bytes. Which end goes first is a genuine design choice, and both answers are in use. Store 0x12345678 starting at address 1000:

  little-endian  (Apple silicon, x86)      big-endian  (network order)

  1000:  78   ← least significant        1000:  12   ← most significant
  1001:  56                              1001:  34
  1002:  34                              1002:  56
  1003:  12                              1003:  78

Little-endian puts the least significant byte at the lowest address. It reads backwards to a human, but it has a concrete advantage: the low byte of a value sits at the same address as the value itself, so narrowing a 64-bit integer to 8 bits is free — you read fewer bytes from the identical pointer, with no offset arithmetic.

Big-endian matches how we write numbers and became the convention for network protocols — which is why it is called network byte order, and why htons/htonl exist in every socket library. Any time bytes cross between machines or go into a file format, somebody has to commit to an order.

Python makes you state it explicitly, which is the right default:

import struct

struct.pack('<I', 0x12345678).hex(' ')   # '78 56 34 12'  little
struct.pack('>I', 0x12345678).hex(' ')   # '12 34 56 78'  big

(0x12345678).to_bytes(4, 'little')          # same thing, no struct

Rust the same, by method name — and to_ne_bytes for whatever the host uses:

0x1234u16.to_le_bytes()   // [0x34, 0x12]
0x1234u16.to_be_bytes()   // [0x12, 0x34]
0x1234u16.to_ne_bytes()   // native — [0x34, 0x12] on Apple silicon

What your processor actually executes

Every operator in altitude 1 is a single ARM64 instruction:

  and   x0, x1, x2      // x0 = x1 & x2
  orr   x0, x1, x2      // x0 = x1 | x2
  eor   x0, x1, x2      // x0 = x1 ^ x2   ("exclusive or", not "xor")
  mvn   x0, x1          // x0 = ~x1       ("move not")
  lsl   x0, x1, #3      // logical shift left
  lsr   x0, x1, #3      // logical shift right  — fills with zeros
  asr   x0, x1, #3      // arithmetic shift right — copies the sign bit
  clz   x0, x1          // count leading zeros
  rbit  x0, x1          // reverse all 64 bits

Note that lsr and asr are different instructions. That is the hardware reason Python's >> behaves differently on negative numbers — signed values need the sign bit replicated, unsigned ones need zeros, and the compiler picks the instruction from the type.

All of these are single-cycle ALU operations, and the core is wide enough to retire several per cycle. This is as cheap as computation gets on real hardware.

Every day in this course ends here: time, space, and where the thing is the wrong choice.

On the hardware: as cheap as it gets

A bitwise operation on a machine word is O(1) — one ALU instruction, roughly one cycle, several able to issue in the same cycle. There is no faster category of computation.

In CPython it is not O(1)

This is the most important cost lesson of the day, and it catches people who have only ever reasoned about bit operations in C.

A Python int is arbitrary precision. CPython stores it as an array of 30-bit digits, so an operation on a big integer is a loop over that array:

For values below 2³⁰ that is one digit, so effectively constant — but with roughly 30–50 nanoseconds of interpreter overhead per operation against something closer to a third of a nanosecond in Rust. A hundredfold constant factor that Big-O cannot see, and the reason day 41 exists.

And 1 << 10000 is not a shift at all in any hardware sense — it is an allocation of a 334-digit integer.

Kernighan versus the naive loop

Same complexity class in the worst case, sixty-four times apart in the case that actually occurs in sparse bitmask code.

An integer as a set, costed

For up to 64 elements, the comparison against a hash set is lopsided:

One complexity result that surprises people

Enumerating every submask of every mask over n elements is O(3ⁿ), not O(4ⁿ) as the nested loop suggests.

The proof is a counting argument. For each of the n bits there are exactly three possibilities across the pair (mask, submask): in both, in the mask only, or in neither. It cannot be in the submask without being in the mask. Three independent choices per bit, n bits, so 3ⁿ pairs total.

When bitmasks are the wrong answer

• More than word-many elements. Past 64 you need a real bitset (bytearray, int with explicit indexing, or a library), and the clean single-register story is gone.
• Sparse universes. Three values drawn from a billion possibilities is a set, not a mask.
• Anywhere a future reader has to decode it. Clever bit-packing in application code that nobody can read is a maintenance liability, not an optimisation. The flags example earlier works because READ, WRITE and DELETE are named.
• Before measuring. If the bit-twiddling is not in a hot path, the clearer code wins by default.

Practice questions

Worth answering before revealing. No interpreter — the point is reading bits in your head.

C    A    F    E
1100 1010 1111 1110

n > 0 and n & (n - 1) == 0

2000: 00   ← least significant
2001: FF
2002: 00
2003: 00

1001_0000  →  1000_0000  →  0000_0000

Coding problems

Both are pure bit manipulation and both rest on the XOR algebra above. Complexity stated before code, every time.

[1,2,1,3,2,5]  →  [3,5]

[3,10,5,25,2,8]  →  28     # 5 ^ 25

Worked solutions land in github.com/Jeevan-Rai/god-of-code alongside the benchmarks and assembly dumps for each day.