Bitwise operations: AND, OR, XOR, NOT and shifts

Computers store integers as bits: a sequence of zeroes and ones. Most of the time we can ignore that representation and use ordinary arithmetic. Bitwise operations are useful when the individual bits are the data—for example, when working with permissions, network protocols, colour channels, hardware registers or compact encodings.

Python has six commonly used bitwise operators:

The easiest way to understand them is to write the operands in binary. We will use four bits for the positive values in the examples:

12 = 1100
10 = 1010

Binary numbers in Python

In the diagrams and table above, bare sequences such as 1100 are binary bit patterns. Python source code needs the 0b prefix to distinguish a binary integer from an ordinary decimal integer:

binary = 0b1100
decimal = 12

assert binary == decimal

The prefix changes how we write the integer, not the value Python stores. Python's built-in bin() function converts an integer to a string using the same notation:

bin(12)  # '0b1100'

A binary integer literal is different from a bytes object. A bytes object is a sequence of whole byte values, where each byte contains eight bits:

data = bytes([0b00001100])

len(data)  # 1 byte
data[0]    # 12

AND: keep selected bits

AND produces 1 only when the bit in both operands is 1:

Applied to our values:

  1100  (12)
& 1010  (10)
------
  1000  (8)

AND is often used with a mask: a value whose 1 bits mark the positions we want to keep. To retrieve the lowest four bits of any integer, use the mask 1111:

value = 0b10110110
mask = 0b00001111

lowest_four_bits = value & mask  # 0b00000110, or 6

The zeroes in the mask clear the upper bits. The ones allow the lower bits through unchanged.

OR: set bits

OR produces 1 when either bit—or both bits—is 1:

  1100  (12)
| 1010  (10)
------
  1110  (14)

This makes OR useful for turning selected bits on without disturbing the others. Imagine that each bit represents an application permission:

READ = 0b001
WRITE = 0b010
EXECUTE = 0b100

permissions = READ | WRITE  # 0b011
permissions |= EXECUTE      # 0b111

We can then use AND to test whether a particular flag is present:

if permissions & WRITE:
    print("Writing is allowed")

XOR: toggle bits

Exclusive OR produces 1 when the bits are different, but 0 when they are the same:

  1100  (12)
^ 1010  (10)
------
  0110  (6)

XOR with 1 flips a bit, while XOR with 0 leaves it alone. That makes a mask useful for toggling flags:

settings = 0b1010
settings ^= 0b0010  # 0b1000: the second bit is now off
settings ^= 0b0010  # 0b1010: applying it again restores it

XOR is reversible: (value ^ key) ^ key == value. This property appears in checksums, error-correcting codes and cryptographic algorithms, although XOR with a repeated key is not secure encryption by itself.

NOT: invert bits

NOT flips every bit:

~ 1100
------
  0011

There is an important catch: an integer does not have a fixed width in Python. Python behaves as though signed integers have an unlimited number of sign bits, so ~x is equal to -(x + 1):

~12  # -13

If we specifically want to invert a four-bit value, we can apply a four-bit mask afterwards:

(~0b1100) & 0b1111  # 0b0011, or 3

NOT is also handy for clearing flags. AND with an inverted mask preserves every bit except the ones selected by that mask:

permissions &= ~WRITE

Shifting bits left and right

A left shift moves every bit to the left and fills the newly opened positions on the right with zeroes:

0011 << 2 = 1100
             ^^
             two new zeroes

For non-negative integers, shifting left by n positions is equivalent to multiplying by 2 ** n:

3 << 2  # 12

The written result may gain up to n significant bits, but it does not always do so. Leading zeroes do not contribute to an integer's value, and zero remains zero however far it is shifted:

   1011 << 2 = 101100
   0001 << 2 = 000100  (the value 4 needs only 3 significant bits: 100)
   0000 << 2 = 000000  (still 0)

Python integers do not have a fixed width, so a left shift does not overflow merely because the result needs more bits. This differs from fixed-width integer types in languages where shifting may discard bits that no longer fit.

What happens during a right shift?

A right shift moves every bit to the right. Bits that move beyond the right-hand end are discarded. Those bits are lost from the result.

11[01] >> 2 = 0011
  ^^
  the rightmost bits are discarded

For a non-negative integer, zeroes fill the newly opened positions on the left. Those leading zeroes are useful in a fixed-width diagram, but they are not part of the integer's minimal representation: bin(3) returns 0b11, not 0b0011, and printing the integer itself displays 3.

For non-negative integers, shifting right by n positions is equivalent to floor division by 2 ** n:

13 = 1101
13 >> 2 = 0011  = 11  # 3
13 // (2 ** 2)        # 3

The discarded bits explain why this is floor division rather than exact division. 1101 is 13; its discarded 01 represents the remainder 1, leaving 0011, or 3.

Does >> n always remove n bits?

It moves the pattern right by exactly n positions, but the number of significant bits does not always decrease by exactly n:

1101 >> 2 = 0011  (13 becomes 3: 4 significant bits become 2)
1000 >> 2 = 0010  (8 becomes 2: 4 significant bits become 2)
0010 >> 2 = 0000  (2 becomes 0: it cannot become shorter than zero)
0000 >> 2 = 0000  (0 remains 0)

If n is at least the number of significant bits in a positive integer, all its 1 bits are discarded and the result is zero:

5 >> 3   # 0: 101 has been shifted completely away
5 >> 100 # 0

There is one further detail for negative Python integers. A right shift fills the left with 1 sign bits rather than zeroes, preserving the negative sign. This is called an arithmetic right shift:

-12 >> 2  # -3
-13 >> 2  # -4, the same as -13 // 4

Unless signed values are specifically involved, it is simplest to picture right shifts using non-negative integers: discard bits on the right and introduce zeroes on the left.

Shifts become especially useful when a larger integer contains several smaller values. A left shift makes empty space for a value; a right shift moves a value into a position where we can read it.

Building masks

Writing a mask in binary is clear when it is small, but we can generate a mask of any width. Start with 1, shift it left by the required width, then subtract one:

width = 4
mask = (1 << width) - 1

print(f"{mask:04b}")  # 1111

Why does this work? 1 << 4 is 10000. Subtracting one turns the lower four positions into ones: 01111.

This pattern brings AND, OR and shifts together. It is also the key to the following bit-fiddling example.

Example: packing a string into bits

Suppose we want to encode a string containing only a small set of characters. A normal UTF-8 string uses one byte for each of the ASCII characters below. If there are no more than 16 distinct characters, however, each character can be represented by a number from 0 to 15—and that requires only four bits.

The following program builds a mapping for the characters it encounters, packs their numeric values into one integer and finally converts that integer to bytes. Decoding performs the operations in reverse:

import math
from typing import Any


def get_mapping_from_chars(characters: set[str]) -> dict[str, int]:
    return {character: i for i, character in enumerate(sorted(characters))}


def get_reverse_mapping(mapping: dict[str, int]) -> dict[int, str]:
    return {value: key for key, value in mapping.items()}


def get_bits_per_character(mapping: dict[Any, Any]) -> int:
    """Return the number of bits required to encode a single character."""
    max_value = len(mapping) - 1
    return math.ceil(math.log2(max_value + 1))


def get_bytecount_for_string(input_string: str, mapping: dict[str, int]) -> int:
    """Return the number of bytes required to encode the given string."""
    bits_per_character = get_bits_per_character(mapping)
    total_bits = len(input_string) * bits_per_character
    return math.ceil(total_bits / 8)


def encode_string(input_string: str, mapping: dict[str, int]) -> bytes:
    """Encode a string into bytes using the provided mapping."""
    value = 0
    bits_per_character = get_bits_per_character(mapping)

    for char in input_string:
        value = value << bits_per_character
        value = value | mapping[char]

    byte_count = get_bytecount_for_string(input_string, mapping)
    return value.to_bytes(byte_count)


def decode_bytes(
    encoded: bytes,
    character_count: int,
    reverse_mapping: dict[int, str],
) -> str:
    value = int.from_bytes(encoded)
    bits_per_character = get_bits_per_character(reverse_mapping)
    mask = (1 << bits_per_character) - 1
    characters = []

    for _ in range(character_count):
        character_bits = value & mask
        characters.append(reverse_mapping[character_bits])
        value = value >> bits_per_character

    return "".join(reversed(characters))


input_string = "ABCDABCEGEHSKEJWOIEWQOJQWOEJOVOI!"
mapping = get_mapping_from_chars(set(input_string))
reverse_mapping = get_reverse_mapping(mapping)

encoded = encode_string(input_string, mapping)
decoded = decode_bytes(encoded, len(input_string), reverse_mapping)

assert decoded == input_string
print(encoded)
print(decoded)

There are exactly 16 different characters in this input, so each mapped value occupies four bits. Encoding one character works like this:

1. value << 4 shifts the existing data left, making four empty bits at the end.
2. value | mapping[char] inserts the new character's value into those empty bits.
3. Repeating the process joins all the four-bit values into a single integer.

Decoding starts at the other end:

1. (1 << 4) - 1 creates the mask 1111.
2. value & mask retrieves the final four-bit character value.
3. value >> 4 discards that character and brings the next one into position.
4. Characters are extracted from right to left, so the final list is reversed.

The 33-character ASCII string normally occupies 33 bytes. Its packed character data occupies 132 bits, rounded up to 17 bytes. That comparison excludes the mapping and character count, which a self-contained file or network message would also need to store. This technique therefore pays off when the alphabet is known in advance or when enough data shares the same mapping.

That is bit fiddling in practice: shifts position the data, OR puts it in place, and a mask combined with AND takes it out again.