我當時正在玩創建一個小棋子解算器的想法。首先，我會製作一個非常小巧的跳棋板，然後繼續構建遊戲樹等。將64位整數中的每一位比較爲一個32位整數

標準跳棋板具有8行，和4官能列（跳棋只能移動對角線）。這給了我們32個職位！每個位置需要的3位信息... king位，並color位...所以00是非王黑，01是非王衝，10是王黑，11是王衝。這給了我們64這是一個很好的數字來處理（長整數的確切大小）。

但是，每個檢查器還需要一個附加位... isOccupied位，因爲每個檢查器位置可以是空的，或者填充上述四個狀態之一。我決定採用64個狀態，並將它們放入一個長64位的int中，並將這32個狀態放入一個32位整數中。

所以，現在我們有一些背景，我有以下問題：我想輕鬆地說：「這個板上有多少紅色棋子？」那麼這不是那麼糟糕...我們的64位整數保存這樣的數據：

king_color_king_color_king_color所以011001意味着我們有紅色，黑色的國王，紅色。

爲了得到顏色信息，我們可以使用位掩碼01010101 ... 01，它是十六進制的0x5555555555555555。這將國王位清零，只留下顏色位。因此，在與掩碼「與」之後的011001示例中，我們有010001.如果我們計算位數（popcount,bitcount），我們可以得到紅色的數量......

啊，但是等等！這些顏色可能不是「正在使用」。我們必須檢查我們的32位int以查看給定的檢查器是否正在使用中！所以說我們對於我們佔用的32個整數有011個......這意味着第一個檢查者，上面的01（紅色非王）...實際上沒有被佔用......它只是一個空的方塊。如果我們要在那裏移動另一個檢查器，我們可能需要也可能不需要更新這兩個特殊顏色位。所以，把他們放在一起

32bit = 011 
64bit = 011001

代表3個檢查位置...一個空的檢查與以前是紅色，其次是黑王，其次是紅色。一旦我們做了64位掩碼010101操作我們得到：

64bitWithMask = 010001 
32bit=011

天真我們有2個紅色...但我們實際上只有1個活動......我想做些什麼基本上採取奇數位64位的字符串，並將它們與32位字符串中的每一位進行邏輯與運算......即

1 AND 0, 0 AND 1, 1 AND 1給我們001代表紅色檢測器的計數。

或等價地，將64bitWithMask轉換爲64bitWithMaskOddBits = 101 然後簡單地用AND與32位得到011 & 101 = 001。

那麼形式上，有沒有辦法取一個長度爲2X的比特串，並通過只取其奇數比特來將它縮小到長度X？我努力避免循環，ifs等，只使用邏輯（和，或，異或，否定等）。

當然或者，如果有另一種戰略，以獲得給我的32位和64位串紅的正確計數。謝謝！

編輯：

的解決我提出的是優雅的接受的答案下面解決了這個問題，但我的實際應用中更好的解決方案是對64位代表分成兩個32這節省了我一堆的操作來提取我需要的東西。感謝LukeG和Tehtmi的幫助！我很高興能夠接觸到這種位操作的新技術，「平行」。

來源

2017-07-28 user2770791

在奇數位上移位運算符，並使用適當的掩碼進行AND – Ripi2

或者您可以將這些圖層分開存儲在首位。你爲什麼不使用一個32位整數作爲王位，一個是彩色位，另一個是佔位位？ – 2017-07-29 00:01:16

爲什麼不將數據存儲在兩個64位整數中？好吧，這會留下32位未使用，但您也可以組織如何使用/設置位，以便進行簡單的按位比較。或者簡單地使用3個32位整數，而不是在64位變量中交錯。 – Peter

將數字中的每一位都壓縮成半長數字有點棘手，因爲每一位需要移位一個不同的數量。但是，有一種聰明的方式來完成，它需要的操作少於單獨處理每一位的操作。對於64位，它看起來像這樣（僞代碼）：

x = x & 0x5555555555555555 
// or for the alternate bits: x = (x >> 1) & 0x5555555555555555 
x = (x | (x >> 1)) & 0x3333333333333333 
x = (x | (x >> 2)) & 0x0f0f0f0f0f0f0f0f 
x = (x | (x >> 4)) & 0x00ff00ff00ff00ff 
x = (x | (x >> 8)) & 0x0000ffff0000ffff 
x = (x | (x >> 16)) & 0x00000000ffffffff

這裏所發生的事情的位在一個32位的數字的每個步驟的圖示（初始掩模之後）：

0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p 
00ab00cd00ef00gh00ij00kl00mn00op 
0000abcd0000efgh0000ijkl0000mnop 
00000000abcdefgh00000000ijklmnop 
0000000000000000abcdefghijklmnop

例如，位g需要向右移動9，所以請查看兩個冪的組件9 = 1 + 8。因此，g在>> 1步驟和>> 8步驟被移位。

這種比特算法有時被描述爲「並行」。您可能有興趣查看此famous list。（它包括與這裏發生的事情密切相關的交錯）。

這種代碼的標準免責聲明是通常很難處理，所以它可能不應該用在嚴肅的項目中，除非存在實際上是一個性能問題（即使如此，確保清楚代碼應該做什麼，例如註釋）。如果沒有性能問題並且您仍然想使用位操作，那麼循環解決方案可能仍然是首選，因爲它更易於理解和使用。

來源

2017-07-29 03:50:11 tehtmi

太棒了！這更像我在我原來的問題中想要的。我需要更多地研究你的插圖來真正體會它，爲自己嘗試一個小例子。在這種情況下，我只是試圖製作一個非常快速的小巧跳棋板，因爲在遊戲樹中會有數千個或更多的棋盤。此外，它就像一個謎題，將「正常」人類邏輯轉換爲位邏輯（如多路複用以避免分支）。我已經把64位分成了兩個32位，但是感謝你對如何做到這一點的見解！ – user2770791

更改爲接受的答案，因爲這解決了我的實際問題（而不是顯而易見的一個非常明顯的解決方法）。 – user2770791

我看不出有什麼辦法做到這一點不使用循環。

編輯：我被證明是錯誤的tehtmi。我仍然認爲在這個答案結尾提出的「替代解決方案」是解決手頭問題的更好方法，tehtmi提出了一個非常有趣的解決方案，如果你還沒有，你應該向上滾動並向上投票。

我看到兩種方法可以解決這個。

第一個，它來靠近你想要達到的目標，就是：

uint32_t occupied; 
uint64_t data; 

uint32_t occupiedWithRed; 
for (auto i = 0; i < 32; ++i) { 
    occupiedWithRed |= (data >> i) & occupied & (1 << i); 
}

的紅色位置的數量將是occupiedWithRed設置位的計數。

的容易多了（可能更快）的做法是：

uint32_t occupied; 
uint64_t data; 

auto count = 0; 
for (auto i = 0; i < 32; ++i) { 
    if ((data >> (2 * i)) & (occupied > i)) ++count; 
}

或者，做一些完全不同的：正如在評論中指出的，如果你能減輕你的生活你分開你在3個不同的32個數據位無符號整數。一個用於區分紅黑相間，一個用於區別自由和被佔領，一個用於區分國王和非國王。這樣你的任務將變得更加容易。這將是一個單位的問題，並計算漢明重量。

來源

2017-07-29 00:01:24 LukeG

正如SergeyB所評論的那樣，並且由你重申，將它分解爲3個32位整數是一個更容易的解決方案......我用「噢，64位完全適合長時間」來實現這個事實，以實現2個32位整數讓一切變得更簡單....我覺得很愚蠢。這樣我就不需要上面提到的循環。非常感謝你花時間陪伴！ – user2770791

而是收集偶數或奇數位與32位的佔用比較，我寧願走另一條路，並將它們分配到一個64位整數，他們去只在奇數位置的。另外，我會將它們轉移到另一個64位整數的偶數位置。

然後，您可以輕鬆地將位置信息整數中的奇數位或偶數位佔用整數與偶數位或奇數位進行比較。

來源

2017-07-29 00:05:38 bjhend

將64位整數中的每一位比較爲一個32位整數

編輯：

回答

相關問題