Binary Arithmetic and Bitwise Operations

What binary is, and the basic recipe for two's complement, are on Number Systems and Data Representation; the logic of AND, OR and XOR on single true/false values is on Boolean Logic. This page is about calculating with whole bit patterns, and why the tricks work.

Bit positions

Number the bits of a binary number from the right, starting at 0. Bit i has the weight 2^i, so in 10110010_2 bit 1 is worth 2 and bit 7 is worth 128. The rightmost bit, bit 0, is the least significant bit (LSB): changing it changes the value by only 1, and it alone decides whether the number is even or odd. The leftmost bit of a value with a fixed width is the most significant bit (MSB), the one with the largest weight; in an 8-bit value that is bit 7, worth 128.

Numbering from 0 matches the exponent: bit i is worth 2^i. Documents that number bits from 1, or from the left (as some network standards do), say so explicitly, so always check the convention.

Binary addition

Add column by column from the right, exactly as with decimal numbers. There are only four cases per column:

A carry is the extra 1 that moves to the next column on the left when a column's sum does not fit in one digit, just like carrying the 1 in 7 + 5 = 12 in decimal. Worked example, 1011 + 0110 (11 + 6):

carry     1 1 1
            1 0 1 1      11
          + 0 1 1 0       6
          ---------
          1 0 0 0 1      17

1. Bit 0: 1 + 0 = 1. Write 1, no carry.
2. Bit 1: 1 + 1 = 10. Write 0, carry 1.
3. Bit 2: 0 + 1 + carry 1 = 10. Write 0, carry 1.
4. Bit 3: 1 + 0 + carry 1 = 10. Write 0, carry 1.
5. The final carry becomes a new bit 4. Result 10001_2 = 16 + 1 = 17. Correct.

In hardware, one column is a full adder: XOR gives the sum bit and AND/OR logic gives the carry (the simpler half adder is built on Worked example: a half adder). A 64-bit adder chains 64 of them.

Multiplying: shift and add

Multiplication by a single binary digit is trivial: times 1 copies the number, times 0 gives 0. So long multiplication in binary is nothing but shifted copies added up. Worked example, 1011 × 101 (11 × 5):

          1 0 1 1      11
        ×   1 0 1       5
        ---------
          1 0 1 1      1011 × 1
        0 0 0 0        1011 × 0, shifted one place
      1 0 1 1          1011 × 1, shifted two places
      -----------
      1 1 0 1 1 1      55

a, b = 0b1011, 0b0110
print(a, b, a + b, bin(a + b))
print(bin(0b1011 * 0b101), 0b1011 * 0b101)
print(bin(0b1011 + (0b1011 << 2)))     # shift and add: 1011 x 101

11 6 17 0b10001
0b110111 55
0b110111

Negative numbers: why two's complement works

The recipe for two's complement (invert all bits, add 1) is on Two's complement. Here is the mathematics behind it. In n bits, two's complement stores a negative number -x as the pattern for

In 8 bits, −5 is stored as 256 - 5 = 251 = 11111011_2. Why does "invert and add 1" produce that?

1. Inverting every bit of x gives 11111111_2 - x, because each bit becomes 1 minus itself. And 11111111_2 = 2^8 - 1, in general 2^n - 1.
2. So the inverted pattern is (2^n - 1) - x.
3. Adding 1 gives 2^n - x. That is exactly the stored value.

The leftmost bit acts as the sign bit: it is 1 for every negative number and 0 for zero and the positive numbers. In two's complement it is not a separate "minus" flag but a place value of its own, with a negative weight: -2^{n-1}. For 11111011_2: -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5. That gives the range of an n-bit signed integer:

For 8 bits that is −128 to 127; for 32 bits −2,147,483,648 to 2,147,483,647. There is one more negative number than positive, because zero takes one of the patterns with sign bit 0.

def twos(value, bits=8):
    return format(value & (2 ** bits - 1), f"0{bits}b")

for v in (5, -5, -1, -128, 127):
    print(f"{v:>5} -> {twos(v)}")
print(int("11111011", 2) - 256)

    5 -> 00000101
   -5 -> 11111011
   -1 -> 11111111
 -128 -> 10000000
  127 -> 01111111
-5

value & (2 ** bits - 1) keeps the lowest 8 bits of Python's unlimited integer, which for a negative number gives exactly 2^n - x. The last line goes back: a pattern with the sign bit set is worth its unsigned value minus 2^n.

Subtraction is addition

The payoff: a - b equals a + (2^n - b) once you drop the bit that does not fit, because adding 2^n and then dropping it changes nothing within n bits. Worked example, 7 − 5 in 8 bits:

1. −5 is stored as 251 (11111011).
2. 7 + 251 = 258, which needs 9 bits: 1 0000 0010.
3. Drop the ninth bit (subtract 256): 00000010 = 2. Correct.

So a processor needs only an adder and an inverter to subtract, and the same adder works for signed and unsigned numbers. The bits are the same; only the interpretation differs.

Overflow as arithmetic modulo 2ⁿ

A fixed-width integer with n bits can only hold 2^n patterns, so the hardware keeps the lowest n bits of every result and drops the rest. Mathematically, it calculates modulo 2^n: the result is the remainder after dividing by 2^n (see Modular Arithmetic). When the true result does not fit, the value wraps around: that is overflow (the general idea, with a C example, is on Overflow).

• Unsigned: 200 + 100 = 300 in 8 bits becomes 300 − 256 = 44.
• Signed: 100 + 100 = 200 does not fit in −128…127. The pattern for 200 is read as 200 − 256 = −56: two positive numbers gave a negative result. Signed overflow has happened exactly when both operands have the same sign and the result has the other sign.

def add_8bit(a, b):
    return (a + b) % 256

def as_signed_8bit(pattern):
    return pattern - 256 if pattern >= 128 else pattern

print(add_8bit(200, 100))
print(add_8bit(7, 256 - 5))                       # 7 - 5 as 7 + (-5)
print(as_signed_8bit(add_8bit(100, 100)))         # signed overflow

44
2
-56

Python's own integers never overflow; they grow as needed. C, C# and Java use fixed widths, and wrap or fail depending on the language and settings (see Overflow and checked in C# and Overflow in Java).

Worked example: a wrapping traffic counter

Network monitoring reads an interface's byte counter every 60 seconds and divides the difference by the time to get the traffic rate. A 32-bit counter wraps after 2^{32} = 4{,}294{,}967{,}296 bytes. Tomasz Nowak in the network operations center (NOC) sees two readings: 4,294,000,000 and then 300,000,000. The second is smaller, so the counter has wrapped.

1. A plain subtraction gives a negative number: 300,000,000 − 4,294,000,000 = −3,994,000,000.
2. Counting modulo 2^{32} repairs it: add 2^{32} to get 300,967,296 bytes. In Python, (new - old) % 2**32 does this for both the wrapped and the normal case.
3. Rate: 300,967,296 × 8 bits / 60 s ≈ 40.13 Mbit/s.

COUNTER = 2 ** 32                       # a 32-bit byte counter wraps here
old, new = 4_294_000_000, 300_000_000   # two readings 60 seconds apart
sent = (new - old) % COUNTER
print(sent, "bytes")
print(f"{sent * 8 / 60 / 1e6:.2f} Mbit/s")
print(f"wraps after {COUNTER * 8 / 1e9:.1f} s at 1 Gbit/s")

300967296 bytes
40.13 Mbit/s
wraps after 34.4 s at 1 Gbit/s

The last line shows the limit of the trick: on a busy 1 Gbit/s link a 32-bit byte counter can wrap more than once between two readings a minute apart, and then no calculation can recover the true number. That is why monitoring fast links uses 64-bit counters.

from datetime import datetime, timezone

print(2 ** 31 - 1)
print(datetime.fromtimestamp(2 ** 31 - 1, tz=timezone.utc))

2147483647
2038-01-19 03:14:07+00:00

Bit shifts

A bit shift moves every bit of a number a fixed number of positions to the left or right. Shifting left by one adds a 0 at the right, so every bit's weight doubles:

"x shifted left by k is x times 2 to the k; x shifted right by k is x divided by 2 to the k, rounded down." Shifting right drops the k lowest bits, which is why the result is rounded down. It is the same as appending or removing zeros in decimal, which multiplies or divides by 10.

• 1 << 10 is 2^{10} = 1024: the usual way to write a power of 2 in code.
• 1000 >> 3 is \lfloor 1000/8 \rfloor = 125.
• For negative numbers, Python's >> is an arithmetic shift: it copies the sign bit in from the left, so -16 >> 2 is −4 and the result still rounds down. A logical shift fills with zeros instead; Java and JavaScript have both (>> and >>>).

print(1 << 10, 1000 >> 3, 1000 // 8, -16 >> 2)
print(1 << 2 + 1, (1 << 2) + 1)

1024 125 125 -4
8 5

Bitwise operations and masks

The bitwise operators apply a logic operation to each pair of bits in the same position, all positions at once. Python writes them & (AND), | (OR), ^ (XOR) and ~ (NOT); they are introduced on Bitwise operators, and the difference with and/or on Bitwise versus logical operators.

        1100          1100          1100
    AND 1010      OR  1010      XOR 1010
        ----          ----          ----
        1000          1110          0110

A bit mask is a value whose 1 bits mark the positions you want to work on. Combined with an operator, it selects, sets, clears or flips exactly those bits and leaves the others alone:

Subnet masks

A subnet mask is a bit mask with ones for the network part of an address and zeros for the host part. Worked example: which network does 192.0.2.130/26 belong to, and what is its broadcast address?

1. /26 means 26 one-bits: 255.255.255.192. The first three octets of the mask are all ones, so the address's first three octets stay as they are (192.0.2).
2. Last octet: 130 = 10000010 and 192 = 11000000. AND keeps only the first two bits: 10000000 = 128. The network address is 192.0.2.128.
3. The broadcast address sets all host bits to 1: OR the address with the inverted mask (00111111 = 63): 10000010 OR 00111111 = 10111111 = 191. Broadcast: 192.0.2.191.

import ipaddress

ip = int(ipaddress.IPv4Address("192.0.2.130"))
mask = int(ipaddress.IPv4Address("255.255.255.192"))
print(ipaddress.IPv4Address(ip & mask))
print(ipaddress.IPv4Address(ip | (~mask & 0xFFFFFFFF)))
print(bin(mask).count("1"))
net = ipaddress.ip_network("192.0.2.130/26", strict=False)
print(net, net.broadcast_address, net.hostmask)

192.0.2.128
192.0.2.191
26
192.0.2.128/26 192.0.2.191 0.0.0.63

The number of one-bits in the mask is the prefix length (26). The inverted mask, 0.0.0.63, is the host mask; Cisco access lists use the same inverted pattern as a wildcard mask (see Wildcard masks). The quick mental method with block sizes is on The block size method; it is the same AND, done in decimal.

Try it: AND an address with a mask

Enter an address and a subnet mask to see the AND that gives the network address and the OR with the inverted mask that gives the broadcast address, bit by bit.

Permission bits and umask

Linux permissions are nine bits, written as three octal digits: 754 is 111 101 100 (see Permission bits in depth). The umask is a mask of permissions to take away from new files: the result is mode & ~umask, a "clear bits" operation (see Default permissions: umask). Worked example: a new file requests 666 and the umask is 022.

1. In binary, 666 is 110 110 110 and 022 is 000 010 010.
2. Inverted, the umask is 111 101 101: ones everywhere except the write bits for group and others.
3. AND: 110 110 110 & 111 101 101 = 110 100 100, which is 644 in octal: read-write for the owner, read-only for the rest.

mode = 0o666
umask = 0o022
print(oct(mode & ~umask))
perm = 0o754
print(bool(perm & 0o100), bool(perm & 0o002))   # owner execute? others write?
print(format(perm, "09b"))
flags = 0b0000
flags |= 0b0100        # set bit 2
flags ^= 0b0001        # toggle bit 0
flags &= ~0b0100       # clear bit 2
print(format(flags, "04b"))

0o644
True False
111101100
0001

The last four lines show the same three operations on a set of feature flags stored in one integer, a common pattern in file formats, network protocol headers and APIs.

XOR undoes itself

XOR has a property that the other operations lack: applying the same value twice cancels out. a \oplus b \oplus b = a, because b \oplus b = 0 and a \oplus 0 = a. It is also commutative and associative, so the order does not matter. That makes XOR the basis of RAID parity: store the XOR of the data blocks, and if one disk fails, XOR the surviving blocks with the parity to rebuild it (see Parity and Error Detection and Correction).

disks = [0b10110010, 0b01101100, 0b11100001]
parity = disks[0] ^ disks[1] ^ disks[2]
print(format(parity, "08b"))
rebuilt = disks[0] ^ disks[2] ^ parity          # disk 1 has failed
print(format(rebuilt, "08b"), rebuilt == disks[1])

00111111
01101100 True

Useful bit tricks

A few identities come up again and again in low-level code, networking and job interviews. The first two follow from how binary subtraction borrows.

• x & (x - 1) clears the lowest 1-bit. Subtracting 1 turns the lowest 1 into 0 and all the zeros to its right into ones; the AND then wipes out that whole tail. A power of 2 has exactly one 1-bit, so x & (x - 1) == 0 (for x \gt 0) tests for a power of 2.
• x & -x keeps only the lowest 1-bit. In two's complement, -x is ~x + 1, which matches x at the lowest 1-bit and differs everywhere to its left.
• x & 1 is the LSB: 1 for odd numbers, 0 for even ones.
• Modulo a power of 2 is a mask: x \bmod 2^k is x & (2**k - 1) for non-negative x, because the bits above position k - 1 are all multiples of 2^k. Hash tables with a power-of-2 size use this to pick a bucket quickly.
• Counting bits: int.bit_count() (Python 3.10+) counts the ones (also called the popcount, as in the prefix length of a mask), and int.bit_length() gives the position of the highest one plus 1.

for n in (64, 100, 2027):
    print(f"{n:>4}: power of 2? {n & (n - 1) == 0!s:<5}  lowest set bit {n & -n:>2}"
          f"  odd? {n & 1 == 1!s:<5}  n % 16 = {n % 16:>2} = n & 15 = {n & 15:>2}")
print((2026).bit_count(), (2026).bit_length())
print(~5, ~5 & 0xFF)

  64: power of 2? True   lowest set bit 64  odd? False  n % 16 =  0 = n & 15 =  0
 100: power of 2? False  lowest set bit  4  odd? False  n % 16 =  4 = n & 15 =  4
2027: power of 2? False  lowest set bit  1  odd? True   n % 16 = 11 = n & 15 = 11
8 11
-6 250

Where binary arithmetic shows up in IT

• Networking: network and broadcast addresses, prefix lengths, wildcard masks and route summarization are all AND, OR and NOT on 32-bit (IPv4) or 128-bit (IPv6) numbers.
• Operating systems: permission bits, umask, process and file flags.
• Monitoring: wrapping counters, computed modulo 2^{32} or 2^{64}.
• Storage and transmission: XOR parity in RAID, checksums and CRCs that detect corrupted bits.
• Programming: overflow bugs, sign errors when mixing signed and unsigned types, flags in one integer, fast multiplication and division by powers of 2.