BitsAlgorithmaka AND OR XOR NOT, bit shifts, bitwise logic

Bitwise Operators

The six primitive operations on the binary representation of integers: AND, OR, XOR, NOT, left shift and right shift.

▶ VisualizePattern: Bit ManipulationPractice (3)
Progress

Overview

Every integer is stored as a fixed-width string of bits. Bitwise operators act on those bits independently and in parallel: & (AND), | (OR), ^ (XOR) combine two integers bit by bit, ~ (NOT) flips every bit of one integer, and << / >> slide the whole bit pattern left or right.

Truth tables per bit position: AND 0&0=0, 0&1=0, 1&0=0, 1&1=1 (1 only if both are 1). OR 0|0=0, 0|1=1, 1|0=1, 1|1=1 (1 if either is 1). XOR 0^0=0, 0^1=1, 1^0=1, 1^1=0 (1 if the bits differ). NOT ~0=1, ~1=0.

Shifts are multiplication and division by powers of two: x << k equals x * 2^k (bits fall off the top), x >> k equals floor(x / 2^k) for non-negative x. Example: 13 = 1101b, 13 << 1 = 11010b = 26, 13 >> 1 = 110b = 6.

Signed integers use two's complement: the top bit has weight -2^(w-1), so -1 is all ones and ~x == -x - 1. Because of this, right shift comes in two flavors. An arithmetic shift copies the sign bit into the vacated positions (-8 >> 1 == -4), preserving the sign and implementing floor division. A logical shift fills with zeros (-8 >>> 1 in JavaScript is 2147483644). Java and JavaScript spell them >> and >>>; C++ and Go apply arithmetic shift to signed types and logical shift to unsigned types; Python integers are unbounded, so >> is always arithmetic and there is no >>>.

binaryANDORXORshifttwo's complementO(1)

Intuition

A mental model before the formal terms.

Picture two rows of light switches lined up above each other. AND lights a bulb in a column only when both switches are on — it is a filter that keeps only what both share. OR lights it when either is on — it merges. XOR lights it when the switches disagree — it measures difference, and flipping the same switch twice cancels out.

A shift is sliding the whole row of switches sideways: each slot to the left doubles the value because binary place values double, and each slot to the right halves it, dropping the remainder.

How it works

  1. Write both operands in binary with the same width (32 or 64 bits in most languages; arbitrary in Python).
  2. Apply the operator column by column; there is no carry, so every column is independent — this is why the operations are single CPU instructions.
  3. For shifts, move every bit k positions; bits shifted past the edge are discarded, incoming bits are 0 (left shift, logical right shift) or a copy of the sign bit (arithmetic right shift).
  4. Interpret the result as unsigned or two's-complement signed according to the type. The bit pattern is identical; only the reading differs.

Why it works

Binary place value: bit i has weight 2^i. Shifting left by one moves each bit to weight 2^(i+1), exactly doubling the sum. Shifting right by one halves every weight and discards the 2^0 term, which is floor division by 2.

Two's complement makes addition of negative numbers the same circuit as for positives, and it makes arithmetic right shift equal to floor division: -7 >> 1 == -4, matching Python's -7 // 2, not C's truncating -7 / 2 == -3.

AND with a mask isolates bits, OR with a mask forces bits on, XOR with a mask flips bits. All three are their own inverses in the sense used by masks: (x ^ m) ^ m == x, and x & m never sets a bit that was not set.

Recognition

How to tell a problem wants this.

  • The problem talks about binary representation, bits, parity, or "without using arithmetic operators".
  • A set of at most ~60 boolean flags must be stored compactly or compared quickly — see Bit Masks.
  • You need a cheap multiply or divide by a power of two, or you must test whether an integer is odd (x & 1).
  • Constraints such as n ≤ 20 with "all subsets" suggest bitmask enumeration — see Subset Generation with Bitmasks.
“parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

a
0
7
0
6
0
5
0
4
1
3
1
2
0
1
0
0
= 12
b
0
0
0
0
1
0
1
0
= 10
1/8Start with a=12 (00001100) and b=10 (00001010). Bit 0 on the right is the least significant; each operator works bit by bit.
Bits being examinedResult bit is 1Result bit is 0
PseudocodeLearn Bitwise Operators →
1a & b   # 1 only where both bits are 1
2a | b   # 1 where either bit is 1
3a ^ b   # 1 where bits differ
4~a      # flip every bit (8-bit view)
5a << 1  # shift left: doubles, drops the top bit
6a >> 1  # shift right: halves, drops the low bit
Variables
a12
b10
Complexity
best O(1)
avg O(1)
worst O(1)
space O(1)
Speed

Pseudocode

1AND(a, b): for each bit i: result[i] = a[i] and b[i]
2OR(a, b):  for each bit i: result[i] = a[i] or b[i]
3XOR(a, b): for each bit i: result[i] = a[i] != b[i]
4NOT(a):    for each bit i: result[i] = not a[i]   // == -a - 1 in two's complement
5SHL(a, k): result = a * 2^k, top k bits discarded
6SHR(a, k): arithmetic: floor(a / 2^k), sign bit copied in
7           logical:    unsigned a / 2^k, zeros shifted in

Implementations

11 · The six operators on fixed-width integers
2# Python ints are unbounded: ~a == -a - 1 and >> is always arithmetic.
3def demo(a: int, b: int) -> dict[str, int]:
4    return {
5        "and": a & b,
6        "or": a | b,
7        "xor": a ^ b,
8        "not": ~a,       # -a - 1
9        "shl": a << 2,   # a * 4, never truncated
10        "shr": a >> 2,   # arithmetic (floor division by 4)
11    }
12 
13 
142 · Logical right shift via an unsigned type
15def logical_shift_right(a: int, k: int, width: int = 32) -> int:
16    # There is no >>>; mask to the width first to emulate an unsigned value.
17    return (a & ((1 << width) - 1)) >> k
18 
19 
203 · Two's-complement rendering
21def to_binary(x: int, width: int = 8) -> str:
22    return format(x & ((1 << width) - 1), f"0{width}b")
23 
24 
254 · Demo
26if __name__ == "__main__":
27    print(demo(13, 6))                  # and 4, or 15, xor 11, not -14, shl 52, shr 3
28    print(logical_shift_right(-8, 1))   # 2147483644
29    print(-8 >> 1)                      # -4
30    print(to_binary(-1))                # 11111111
31    wide = 1 << 40                      # no BigInt needed
32    print(wide, bin(wide | 3))
Walkthrough
  1. Python int has no fixed width, so a << 2 never truncates and ~a is exactly -a - 1.
  2. There is no >>>; masking with (1 << width) - 1 first turns a negative number into its unsigned bit pattern, after which >> behaves logically.
  3. format(x & mask, "08b") prints the two's-complement pattern of a negative number restricted to width bits.
  4. 1 << 40 just works — no BigInt, no unsigned long long.
Complexity (this implementation)
time O(1) · space O(1)

Operations cost O(number of 30-bit digits) for big ints, effectively O(1) for values below 2^60.

Language notes
  • bin(x) for negative x yields "-0b...", not a two's-complement string; mask first.
  • int.bit_length() and int.bit_count() (3.10+) are the built-ins for highest bit and popcount.
  • Negative shift counts raise ValueError; there is no undefined behavior anywhere in Python integer arithmetic.
Common mistakes in this language
  • Expecting ~x & 0xFF and ~x to be equal — the first is an 8-bit pattern, the second a negative int.
  • Emulating 32-bit wraparound (e.g. for hash functions) and forgetting to mask after every << or *.
  • Precedence: x & 1 == 0 is x & (1 == 0) in Python too.
Language differences that matter here
  • Width: JavaScript/TypeScript bitwise operators coerce to signed 32-bit (1 << 31 is negative, 1 << 32 is 1); Python ints are arbitrary precision so nothing is ever truncated; C++ uses the operand type (int, unsigned, long long, uint64_t).
  • Logical right shift: JS/TS have >>>; C++ shifts unsigned types logically and signed types arithmetically; Python has no >>> — mask to the width first, then >>.
  • Undefined behavior: C++ shifting by >= the width or by a negative count, and left-shifting negatives before C++20, is UB. JS wraps the shift count mod 32; Python raises ValueError for negative counts and otherwise just computes the value.
  • Values above 32 bits: JS/TS need BigInt (with n suffix; no >>>); C++ needs long long / uint64_t with LL/ULL literal suffixes; Python needs nothing.

Complexity

Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(1)

Each operator is one machine instruction on fixed-width integers. Python big ints cost O(number of digits).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Testing parity (x & 1), multiplying or dividing by 2^k, or extracting fields packed inside an integer.
  • Representing a small set of booleans as one integer so that union, intersection and membership are single instructions — see Bit Masks.
  • Cancelling paired values with XOR — see XOR Patterns.
Avoid it when
  • As a "clever" replacement for * 2 or / 2 in ordinary code: compilers already do this and x >> 1 is wrong for negative x if truncation toward zero was intended.
  • When integers exceed the language's bitwise width — JavaScript silently truncates to 32 bits, so 2 ** 40 | 0 is 0.
  • When readability matters more than nanoseconds; a named boolean array beats an opaque mask in application code.

Alternatives

Bit MasksHash SetArray

Common mistakes

  • JavaScript/TypeScript: applying &, |, << to values above 2^31 - 1 — they are coerced to signed 32-bit, so 1 << 31 is -2147483648 and 1 << 32 is 1. Use BigInt or Math.pow for wider values.
  • Confusing >> (arithmetic) with >>> (logical) on negative numbers, or expecting >>> to exist in Python, C++ or Go.
  • Operator precedence: x & 1 == 0 parses as x & (1 == 0) in C-family languages. Always parenthesize: (x & 1) == 0.
  • Shifting by the full width or more (1 << 32 on a 32-bit int) — undefined behavior in C++, wraps mod 32 in Java and JavaScript.
  • Using ~ to mean logical NOT; ~0 is -1, which is truthy.

Interview patterns

  • Check odd/even with n & 1; check power of two with n & (n - 1) == 0 — see Power-of-Two Tricks.
  • Add two integers without +: carry is (a & b) << 1, sum without carry is a ^ b, loop until carry is 0.
  • Reverse the bits of a 32-bit integer by peeling off the low bit and pushing it into the result 32 times.
  • Hamming distance between two integers is the popcount of a ^ b — see Count Set Bits (Popcount).

Example problems

Single NumbereasyCounting BitseasyBit Counting Trickseasy