Released · improving
Algorithm
Bit manipulation treats integers as binary digits and uses AND, OR, XOR and shifts to handle sets, flags and bitmask DP quickly and compactly.
Bit manipulation views an integer as a row of 0s and 1s and uses AND, OR, XOR, NOT and shifts to read, set, clear and flip individual bits. Computers store integers in binary and negative numbers in two's complement, so these operations usually map to a single CPU instruction. A short expression such as x & -x (the lowest set bit) or x & (x - 1) (that bit cleared) can replace an entire loop.
It matters because one integer can represent a set of about 20 items, which makes it easy to visit every subset and to use sets as states in bitmask dynamic programming. Coding interviews regularly feature subset enumeration, XOR properties and popcount, and production code relies on bits for file permissions, feature flags, subnet math, hash tables and bitmap indexes. The rules differ by language, though: Python integers are unbounded, JavaScript converts operands to 32 bits and has >>>, Java also has >>>, and C++ expects unsigned types for safe masks.
Start by converting numbers to binary and two's complement by hand. Then practice the four single-bit operations (set, clear, toggle, test) and print every subset by looping a mask from 0 to 2^n - 1. Move on to submask enumeration and bitmask DP problems such as job assignment or the traveling salesman problem, and finally check the integer width and shift rules of the languages you use.
Negative numbers are stored by flipping every bit and adding 1. Left shifts multiply by 2, right shifts divide by 2, and languages differ on arithmetic versus logical right shifts.
With the mask 1 << i, OR sets bit i, AND NOT clears it and XOR toggles it. x & -x isolates the lowest set bit and x & (x - 1) removes it.
The subsets of n items correspond one-to-one with the integers 0 to 2^n - 1, and union, intersection and difference each take a single bitwise operation.
Count set bits by repeating x &= x - 1 or with a built-in. Because a ^ a = 0, XOR finds the unpaired value and yields Hamming distances and Gray codes.
popcount counts set bits by clearing the lowest one with x &= x - 1 until nothing is left. subsets loops a mask from 0 to 2^n - 1 and picks the items whose bit is set, producing every subset. The last line shows 12 & -12 = 4 (the lowest set bit), 12 & 11 = 8 (that bit cleared) and x ^ x = 0. Run it with python bit_manipulation.py.
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.pySix chapters that take you from installation to the core ideas of Bit manipulation.
Ask questions, share experience and trade opinions about Bit manipulation.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.