Subset representation with bit strings Bitwise Arithmetic Techniques Advent Calendar 2016 Day 1 - prime’s diary [] - fast zeta transformation fast Möbius transformation convolution
S’s i-th is 1?
(S >> j) & 1
- 0-origin and 0 is LSB
Whole set of N elements
(1 << N) - 1
Complementary set (whole set as U)
~S & U
rightmost 1
(x & -x)
Double loop for elements of a given set python
def calcScore(S):
x = S
ret = 0
i = 0
while x:
if x & 1:
for j in range(i):
if (S >> j) & 1:
ret += M[i, j]
x //= 2
i += 1
return ret
subset enumeration of the given set python
def solve(S):
x = S
while x > 0:
print(f"{x:08b}")
x = (x - 1) & S
Is T included in S?
- The common part with the complement of S is empty.
~S & T == 0
Number of 1’s (popcount)
- If 32 bits. c
T = (T & 0x55555555) + ((T >> 1) & 0x55555555);
T = (T & 0x33333333) + ((T >> 2) & 0x33333333);
T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F);
T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF);
T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF);
c
T -= (T >> 1) & 0x55555555;
T = (T & 0x33333333) + ((T >> 2) & 0x33333333);
T = (T + (T >> 4)) & 0x0F0F0F0F;
T = (T * 0x01010101) >> 24;
This page is auto-translated from /nishio/ビット演算 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.