understanding the logic behind swapping ranges of bits

Question

Hello everyone I need a little help understanding the logic behind Swapping ranges of bits algorithm. The "program" swaps given number of consecutive bits in a given positions and It works perfectly , but I need to understand the logic behind it in order to move on to other topics. Here is the source code for the full "program" http://pastebin.com/ihVpseE1 , I need someone to tell me if I am on the right track so far and to clarify one part of the code that I find difficult to understand.

temp = ((number >> firstPosition) ^ (number >> secondPosition)) & ((1U << numberOfBits) - 1); 
result = number ^ ((temp << firstPosition) | (temp << secondPosition));

1. (number >> firstPostion) move the binary representation of a given uint number(5351) to the right(>>) 3 times (firstPosition). So 00000000 00000000 00010100 11100111 (5351) becomes 00000000 00000000 00000001 01001110 , because to my understanding when you shift the bits you loose the digits that falls out of range.Is that correct? Or the bits from the most right side appear on the left side?

2. (number >> secondPosition) I apply the same logic as .1 , but in my case secondPosition is 27 so the number is comprised of only zeroes(0) 00000000 00000000 00000000 00000000 (which is the number 0) I move the bits of the number 5351 to the right 27 times and that results in only zeroes.

3. ((number >> firstPosition) ^ (number >> secondPosition)) I use the ^ operator on 00000000 00000000 00000001 01001110 and 00000000 00000000 00000000 00000000 which results in the number 00000000 00000000 00000001 01001110 aka (((number >> firstPosition) ^ (number >> secondPosition))

4. ((1U << numberOfBits) - 1) THIS is the part I find difficult (if my understanding of 1. 2. 3. is correct) Does ((1U << numberOfBits) - 1) means that

   • 1) Put 1 at position 3 (numberOfBits) and fill the rest with zeroes (0) and then substract 1 from the decimal representation of that number OR
   • 2) Move the binary representation of the number 1 to the left 3 times (numberOfBits) and then substract 1 from the decimal representation of that number

IF my logic so far is correct then we apply the & operator on the result of ((number >> firstPosition) ^ (number >> secondPosition)) and ((1U << numberOfBits) - 1). and I follow the same logic for result = number ^ ((temp << firstPosition) | (temp << secondPosition)); in order to get the result.

Sorry for the long and probably stupid question , but I really cant ask anyone for help except you guys.Thank you all in advance.

Answer 1

The two alternatives you put up for 4. are effectively the same :) The trick is that this produces a string of binary 1s, up to the given numberOfBits - ie. (1 << 3) - 1 produces 7, or 111 in binary - in other words, "give me only the numberOfBits least significant bits".

Basically, you've described this well, if overly wordy.

The result of the first line is a sequence of numberOfBits bits. The value is a xor between the bit sequences starting from the two different indices and numberOfBits long. The and then simply discards the bits higher than numberOfBits.

The second line then exploits the fact that a ^ b ^ a == b, and b ^ a ^ b == a, and the order of operations doesn't matter - the xor operation is commutative.

As long as the two sequences don't overlap and don't cross the decimal point, it should work just fine :)