翻轉硬幣的位操作

Question

我試圖理解這段代碼。我認爲它使用了段樹數據結構的一些變體，但我無法理解此代碼中的任何位操作。

的實際問題是，有N個硬幣，我們有1個動作和1個查詢，該查詢是

1. 要在範圍翻轉硬幣[A，B]
2. 爲了找到頭在範圍的數量[A，B]。

。

#define LEAVES (131072) 
#define MSB_V (0x80000000) 
#define MSB_P (31) 

int it[2 * LEAVES]; 
int A, B; //Query range 

void flip (int i, int min, int max) 
{ 
    if ((min > B) || (max <= A)) 
    { } 
    else if ((min >= A) && ((max-1) <= B)) 
    { it[i] ^= MSB_V; } 
    else 
    { 
     int l = 2 * i; 
     int r = l + 1; 
     int mid = (min + max)/2; 
     it[l] ^= it[i] & MSB_V; 
     it[r] ^= it[i] & MSB_V; 
     it[i] ^= MSB_V; 
     flip(l, min, mid); 
     flip(r, mid, max); 
     it[i] = (it[l] >> MSB_P ? mid - min - (it[l]^MSB_V) : it[l]) + 
       (it[r] >> MSB_P ? max - mid - (it[r]^MSB_V) : it[r]); 
    } 
} 

int count (int i, int min, int max) 
{ 
    int h; 
    if ((min > B) || (max <= A)) 
    { h = 0; } 
    else if ((min >= A) && ((max-1) <= B)) 
    { h = it[i] >> MSB_P ? max - min - (it[i]^MSB_V) : it[i]; } 
    else 
    { 
     int l = 2 * i; 
     int r = l + 1; 
     int mid = (min + max)/2; 
     it[l] ^= it[i] & MSB_V; 
     it[r] ^= it[i] & MSB_V; 
     it[i] ^= MSB_V; 
     it[i] = (it[l] >> MSB_P ? mid - min - (it[l]^MSB_V) : it[l]) + 
       (it[r] >> MSB_P ? max - mid - (it[r]^MSB_V) : it[r]); 
     h = count(l, min, mid) + count(r, mid, max); 
    } 
    return h; 
} 

有人可以請給我什麼是所有這些位操作背後的邏輯

Answer 1

it代表一個完整的二叉樹一些提示;節點1是根，節點k的子節點是2k和2k + 1。

完整的二叉樹的葉子是硬幣。內部節點是面向特定方式（低31位）的硬幣數量和「翻轉」標記（在符號位中）。如果翻轉的市場清晰，則低31位計算節點子樹中擡頭硬幣的數量，而如果翻轉位被設置，則計數尾部硬幣。

雙方find和count在此使用的參數約定是i是被計數或翻轉的節點，min是由該節點所表示的最低索引，並且max是最高的索引。在find和count中的前兩個測試檢查翻轉/計數範圍（由A和B定義）是否與節點i的範圍不相交或包含節點i的範圍。

你flip看到的是：

• 如果[A，B]是[最小值，最大值]脫節，什麼也不做。
• 如果[A，B]包含[min，max]，則翻轉翻轉的標記。
• 否則，對兩個孩子運行flip。一旦我們完成了這個，這裏的不變量就會被破壞;通過在兩個孩子中增加擡頭硬幣的數量來修復它。

你count看到的是：

• 如果[A，B]是[最小值，最大值]不相交，返回0
• 如果[A，B]包含[分鐘，最大值]，返回該節點的計數。
• 否則，加起來我們孩子的數量。