Every integer your computer stores is a sequence of bits - zeros and ones. When you write x = 42 in Python, the CPU does not see the number forty-two. It sees 101010. Understanding this representation is the foundation for every bit manipulation technique, and it gives you access to operations that are dramatically faster than their arithmetic equivalents.

Binary Basics

Each bit position represents a power of 2, starting from the right. The rightmost bit (position 0) represents 2^0 = 1. Position 1 represents 2^1 = 2. Position 2 represents 2^2 = 4, and so on.

The Six Bitwise Operators

AND (&): Both bits must be 1 to produce 1. This is the masking operator - it selects specific bits while zeroing out the rest.

OR (|): Either bit being 1 produces 1. This is the setting operator - it turns specific bits on without affecting others.

XOR (^): Exactly one bit must be 1 to produce 1. This is the toggling operator - it flips specific bits. XOR is the most important operator for interview problems.

NOT (~): Flips every bit. In two's complement, ~n equals -(n+1).

Left Shift (<<): Shifts bits left by k positions, filling with zeros. Each left shift doubles the value.

Right Shift (>>): Shifts bits right by k positions, discarding the rightmost bits. Each right shift halves the value (integer division).

Two's Complement: How Negative Numbers Work

Computers represent negative integers using two's complement. To negate a number, flip all bits and add 1. This system has an elegant property: addition works the same way for positive and negative numbers, so the CPU needs only one addition circuit.

Common Idioms You Will Use Repeatedly

These patterns appear so often that they are worth memorizing:

Each of these runs in O(1) time. They are the building blocks for every technique in this lesson.