Bitwise BasicsThe basic operations

01Why it exists

Reach for it when you see:Flags, switches, permissions, masks, registers, packing things into one integer, changing one bit without touching the rest, one bit per fact, multiplying or dividing by powers of two.

02The core idea

An integer in memory is a row of bits, where bit i stands for 2^i. Treat each bit as an independent switch and a 32-bit integer becomes 32 booleans. All five basic operations work bit by bit: AND (&) gives 1 only where both sides are 1; OR (|) gives 1 where either side is 1; XOR (^) gives 1 only where the two differ; NOT (~) flips everything; and a shift, x << k, pushes the whole row k places left and pads with zeros on the right, which multiplies by 2^k, while x >> k pushes right and drops the lowest k bits, which divides by 2^k and rounds down.

Why getting, setting and clearing a bit never disturbs the others: bit i of the result of these operations depends only on bit i of the two operands, so bits never interfere with each other. For any bit b: b & 1 = b, b & 0 = 0, b | 0 = b, b | 1 = 1, b ^ 0 = b, b ^ 1 = 1 − b. So take a mask 1 << i, which is 1 only at bit i: x | mask sets bit i to 1 while every other bit ORs with 0 and stays as it was; x & ~mask clears bit i to 0 while every other bit ANDs with 1 and stays as it was; x ^ mask flips bit i alone; and (x >> i) & 1 shifts bit i down to the bottom and reads it off. The same holds for w consecutive bits: (1 << w) − 1 is w ones, and shifting it into place gives you the mask for that stretch.

Complexity: on fixed-width integers each operation is a single CPU instruction, O(1) time and O(1) space, with no best or worst case to speak of. The space saving is a constant factor, but not a small one: n booleans in a bool array take n bytes, while packed into bits they take ⌈n / 8⌉. A set of up to 64 elements fits in one 64-bit integer, where intersection is a & b, union is a | b and difference is a & ~b — one instruction each, where a hash set has to compare element by element. Python integers have no width limit, so with very many bits the cost grows with the number of bits, but within 64 bits you can treat it as constant.

There are three pitfalls worth knowing. Precedence: in C++ == binds tighter than &, so x & 1 == 0 really means x & (1 == 0); in both languages + binds tighter than the shifts, so 1 << i - 1 means 1 << (i - 1). Parenthesising everything is the safe habit. Width and overflow: in C++ 1 << 31 runs into the sign bit of a 32-bit int and comes out negative, and 1 << 40 shifts by more than the width, which is undefined behaviour — for 64 bits write 1ull << k. Negatives and two's complement: bitwise operations treat a negative as its two's complement, where −x = ~x + 1 and therefore ~x = −x − 1. In Python ~178 is −179, not 77, so you have to apply & 0xFF yourself, and shifting a negative right rounds down (-7 >> 1 is −4). This lesson is the parts bin for the ones that follow: XOR's cancelling property drives XOR Tricks, n & (n − 1) clearing the lowest set bit drives Counting Bits, and treating an integer as a set to enumerate drives Subset Enumeration.

03The algorithm

1. 1Decide the bit layout: bit 0 is the lowest. Give each boolean a position, and each multi-bit field a start lo and a width w. Write them as named constants, such as READ = 1 << 2.
2. 2Build the mask: a single bit is 1 << i; w consecutive bits are ((1 << w) − 1) << lo; combine several flags with OR, as in READ | WRITE.
3. 3Query with AND: (x >> i) & 1 gives 0 or 1; (x & mask) != 0 means at least one bit in the mask is set, while (x & mask) == mask means all of them are; read a field with (x >> lo) & ((1 << w) − 1).
4. 4Modify: set with x |= mask, clear with x &= ~mask, flip with x ^= mask. Writing a field means clearing before writing: x = (x & ~mask) | (v << lo), where v must be less than 2^w or truncated first.
5. 5Check widths and types: in C++ use unsigned types, write constants as 1u or 1ull, and keep the shift amount below the width; in Python, apply your own & ((1 << w) − 1) when you need a fixed width. Always parenthesise when mixing these with comparisons.

04Interactive demo

A = 178 (10110010) and B = 108 (01101100). Click any cell of A or B to flip that bit, and the AND, OR, XOR, NOT and shift rows below update immediately; in the input rows blue means 1, and in the result rows green means 1 and grey means 0. The top bit of the default A is 1, so A << 1 pushes it out past the eighth bit. The bottom section highlights the selected bit i in yellow: bit 3 is 0 by default, so setting it matches flipping it and clearing it changes nothing. Select bit 1 instead, where A holds a 1, and you can watch clearing and flipping both turn it into 0.

05Code

The four basic functions — get, set, clear and flip a bit — plus reading and writing a multi-bit field. The examples use the same A and B as the interactive demo, then show real uses: Unix permission 754, a GPIO register and an RGB colour code. Python integers have no fixed width, so there is also 32-bit truncation and two's-complement conversion; the C++ version sticks to unsigned types and spells out the precedence and overflow traps in the code itself.

# Bit numbering: bit 0 is the lowest (rightmost) bit, and bit i stands for 2 to the power i
def get_bit(x, i):
    return (x >> i) & 1                  # shift right by i, then read the lowest bit


def set_bit(x, i):
    return x | (1 << i)                  # OR: force bit i to 1


def clear_bit(x, i):
    return x & ~(1 << i)                 # AND with a mask that is 0 only at bit i


def toggle_bit(x, i):
    return x ^ (1 << i)                  # XOR: bit i goes 0 -> 1 and 1 -> 0


# Multi-bit field: starts at bit lo and is w bits wide
def get_field(x, lo, w):
    return (x >> lo) & ((1 << w) - 1)    # (1 << w) - 1 is w ones


def set_field(x, lo, w, v):
    mask = ((1 << w) - 1) << lo
    return (x & ~mask) | ((v << lo) & mask)   # clear that stretch first, then write


# Python ints have no fixed width, so truncate yourself when you need one
def to_u32(x):
    return x & 0xFFFFFFFF                # keep the low 32 bits and read them as unsigned


def to_i32(x):
    x &= 0xFFFFFFFF
    return x - (1 << 32) if x >> 31 else x    # bit 31 set means negative (two's complement)


R, W, X = 4, 2, 1                        # Unix permissions: read 100, write 010, execute 001

if __name__ == "__main__":
    a, b = 0b10110010, 0b01101100        # 178 and 108, the same pair as the demo
    print(a & b, a | b, a ^ b)           # 32 254 222
    print(~a & 0xFF, ~a)                 # 77 -179 (~a equals -a - 1, so mask it yourself)
    print((a << 1) & 0xFF, a >> 1)       # 100 89
    print(get_bit(a, 3), get_bit(a, 4))  # 0 1
    print(set_bit(a, 3), clear_bit(a, 4), toggle_bit(a, 1))   # 186 162 176

    mode = 0o754                         # rwxr-xr--: owner 7, group 5, others 4
    group = get_field(mode, 3, 3)
    print(group, (group & W) != 0)       # 5 False: the group cannot write
    mode = set_field(mode, 0, 3, R | W)  # give others rw-
    print(oct(mode))                     # 0o756

    color = 0xFF8800                     # 0xRRGGBB
    print(get_field(color, 8, 8))        # 136 (green channel 0x88)
    print(hex(set_field(color, 8, 8, 0x44)))   # 0xff4400

    print(-7 >> 1, to_u32(-1), to_i32(0xFFFFFFFE))   # -4 4294967295 -2

06Practice

• LeetCode 190Reverse Bits (read one bit out, write one bit in)Easy
• LeetCode 1009Complement of Base 10 Integer (NOT needs a mask; mind the zero case)Easy
• LeetCode 405Convert a Number to Hexadecimal (take four bits at a time; negatives use two's complement)Easy
• LeetCode 1318Minimum Flips to Make a OR b Equal to c (compare bit by bit)Medium
• LeetCode 318Maximum Product of Word Lengths (a 26-bit integer as a set of letters)Medium
• LeetCode 371Sum of Two Integers (addition without the plus sign)Medium