Publié · en amélioration
Guide Manipulation de bits · 4/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
A single bitwise operation is one machine instruction, so on fixed-width integers it is O(1). What matters is how many times you repeat it and how many states a mask can describe. This chapter compares popcount strategies, measures subset and submask enumeration, and shows where bitmask DP stops being practical.
On w-bit integers, AND, OR, XOR, NOT, shifts, x & -x and x & (x - 1) all take O(1) time and space. Python integers are unbounded, so strictly an operation costs O(b) for a b-bit value, but anything that fits in 64 bits is effectively constant.
| Method | Time | Notes |
|---|---|---|
| Check every bit | O(w) | simplest, always w rounds |
Kernighan (x &= x - 1) | O(k), k = set bits | fast for sparse values, worst case O(w) |
| 8-bit lookup table | O(w / 8) | needs a 256-entry table |
| SWAR parallel sum | O(log w) | branch-free shifts and adds |
| Hardware POPCNT | O(1) | used by int.bit_count, std::popcount, Integer.bitCount |
def popcount_swar(x: int) -> int:
# unsigned 32-bit values only
x = x - ((x >> 1) & 0x55555555)
x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
x = (x + (x >> 4)) & 0x0F0F0F0F
return ((x * 0x01010101) & 0xFFFFFFFF) >> 24
assert all(popcount_swar(v) == v.bit_count() for v in (0, 1, 255, 2**32 - 1, 0xDEADBEEF))If you need the popcount of every number from 0 to n, fill a table in O(n) with bits[i] = bits[i >> 1] + (i & 1).
With n items there are 2^n masks; testing n bits per mask costs O(2^n * n) time. Collecting every subset in a list also costs O(2^n * n) space, while a generator needs only O(n). Rough limits:
| n | 2^n | 2^n * n | Feel |
|---|---|---|---|
| 10 | 1,024 | about 10 thousand | instant |
| 16 | 65,536 | about 1 million | fast |
| 20 |
| about 1.05 million |
| about 21 million |
| tens of ms in C++, seconds in Python |
| 25 | about 33.5 million | about 840 million | impractical in Python |
| 40 | about 1.1 trillion | - | needs meet in the middle |
Looping over every mask and then over its submasks looks like O(4^n), but it is O(3^n): each item is either outside the mask, in the mask only, or in both mask and submask. For n = 15, 3^15 is about 14 million, which is fine.
n = 4
pairs = 0
for mask in range(1 << n):
sub = mask
while True:
pairs += 1
if sub == 0:
break
sub = (sub - 1) & mask
print(pairs, 3 ** n) # 81 81If you only need subsets of size k, scanning all 2^n masks and filtering by popcount still costs O(2^n). When C(n, k) is much smaller than 2^n, generating combinations directly, as itertools.combinations does, costs O(C(n, k) * k). If you need them as masks, Gosper's hack finds the next mask with the same popcount in O(1).
def next_same_popcount(x: int) -> int:
low = x & -x
ripple = x + low
return (((ripple ^ x) >> 2) // low) | ripple
mask, n = 0b0011, 4
while mask < (1 << n):
print(format(mask, "04b"), end=" ") # 0011 0101 0110 1001 1010 1100
mask = next_same_popcount(mask)With 2^n states and n transitions each, a bitmask DP runs in O(2^n * n). When the state is (set, last vertex), as in the traveling salesman problem (Held-Karp), it is O(2^n * n^2) time and O(2^n * n) space. TSP with n = 20 is about 400 million steps: fine in C++, hard in Python. Compared with trying all n! orders, n = 15 means 1.3 trillion versus about 7.4 million.
import math
for n in (10, 15, 20):
print(n, math.factorial(n), (1 << n) * n * n)| Representation | Membership | Union | Memory | Best for |
|---|---|---|---|---|
| Integer bitmask | O(1) | O(1) | w bits | up to 64 items |
Bitset (std::bitset, BitSet) | O(1) | O(n / w) | n bits | thousands to millions of items |
Hash set (set) | O(1) average | O(n) | tens of bytes per item | wide, sparse domains |
| Sorted list | O(log n) | O(n) | one slot per item | when order matters |
Bitwise operations are O(1); the cost comes from repetitions and state counts. Subset enumeration is O(2^n * n), all mask/submask pairs are O(3^n), and bitmask DP is typically O(2^n * n) or O(2^n * n^2). These techniques shine when n is around 20 or less; beyond that, look for a different approach.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.