用XOR交換各個位

我正在閱讀this article用Xor交換各個位以交換給定數字的位。

作爲* 10的交換範圍的示例假設我們有b = 00101111（用二進制表示），並且我們想要將從i = 1開始的n = 3個連續位（右起第二位）與從j = 5開始的3個連續比特;結果將是r = 11100011（二進制）。 *但我無法理解它是如何工作的。
鑑於代碼是用XOR交換各個位

unsigned int i, j; // positions of bit sequences to swap 
unsigned int n; // number of consecutive bits in each sequence 
unsigned int b; // bits to swap reside in b 
unsigned int r; // bit-swapped result goes here 

unsigned int x = ((b >> i)^(b >> j)) & ((1U << n) - 1); // XOR temporary 
r = b^((x << i) | (x << j));

請任何一個清除我如何代碼工作。

來源

2012-09-11 Aalok

允許在步驟做到這一點：（B >> i）及（B >> j）移動要交換是第一位的位。

（（b >> i）^（b >> j））然後對它們進行異或運算。

（（1U < < N） - 1）這個表達式僅僅是1111號1 ... n倍（二進制）

所以總共x是XOR的結果，與所有其他位爲0.

（x < < i）和（x < < j）將這些位移回到其正確的位置。

（（x < < i）|（x < < j））在結果中設置在任一個中設置的所有位。

and b ^（（x < < i）|（x < < j））表示我們用兩個部分的XOR位對XOR進行異或運算。請注意，x^x^y = y所以既然在這兩個部分中原來在xor中出現兩次，但第二部分只有一次，我們得到位交換。

來源

2012-09-11 06:38:15

我對這個陳述感到困惑（（1U << n） - 1）這是什麼意思？ – Aalok

1U是數字1.在將其左移n次後，您將得到2^n。減1是111 ... 1 n次。 –

unsigned int n; //每個序列中的連續位數 –

那麼，它正在使用移位來限制每個操作所影響的位（即將其他位移出畫面以完成工作，並且只能在我們所關心的那些位置上操作）。作爲其中的一部分，它用xor翻轉這些位，將它們移回原處，並通過與原來的x-oring將它們翻轉回原來的位置。 ......並且因爲這與泥漿一樣清晰......

例如，

XX...XX001^XX..XX111 = XX..XX110 (xor the 2 sequences together + trash bits) 
XX..XX110 & 0...0111 = 110 (keep only those bits we care about) 
00101111^11001100 = 11100011 (and magic!)

來源

2012-09-11 06:33:02 CasualT

用XOR交換各個位

回答

相關問題