ビット演算

Sのi番目が1か？

(S >> j) & 1

0-originで0はLSB

要素数Nの全体集合

(1 << N) - 1

補集合(全体集合をUとして)

~S & U

rightmost 1

与えられた集合の要素に対する2重ループ

code:python

def calcScore(S):

x = S

ret = 0

i = 0

while x:

if x & 1:

for j in range(i):

if (S >> j) & 1:

x //= 2

i += 1

return ret

code:python

def solve(S):

x = S

while x > 0:

print(f"{x:08b}")

x = (x - 1) & S

TがSに含まれるか？

Sの補集合との共通部分が空

~S & T == 0

1の個数(popcount)

32ビットなら

code: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);

code:c

T -= (T >> 1) & 0x55555555;

T = (T & 0x33333333) + ((T >> 2) & 0x33333333);

T = (T + (T >> 4)) & 0x0F0F0F0F;

T = (T * 0x01010101) >> 24;

https://gyazo.com/d5c5b3c6c77c4b5b267f2905ab413398