ビット演算

ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime’s diary

• 高速ゼータ変換 高速メビウス変換 畳み込み

Sのi番目が1か？

• (S >> j) & 1
• 0-originで0はLSB

要素数Nの全体集合

• (1 << N) - 1

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

• ~S & U

rightmost 1

• (x & -x)

与えられた集合の要素に対する2重ループ 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

与えられた集合の部分集合列挙 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ビットなら 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;