Bitwise exchange operations

Question

How to exchange bits of given integer number {p, p+1, ..., p+k-1} with {q, q+1, ..., q+k-1} in case where we have an overlap of both bits intervals; p and q are bit's positions:
p != q; k > 1.

Example:

p = 5;
q = 8;
k = 6;
16-bits decimal number 30 000 in binary representation:
01110101 00110000
================before exchange============
     101 001
  110101
================after exchange==============
     110 101
  101001
============================================

How to decide for bit's positions 8, 9 and 10, which bits to put - 110 or 001?

Answer 1

The algorithm, if allowing overlaps, must be a lossy one.

From your example:

01110101 00110000
     |     |
     101 001
  |    |
  110101

If you swap them, the values are:

01110101 00110000
     |     |
     110 101
     *** - Mismatch!
  |    |
  101001
     *** - Mismatch!

No matter what, if you allow an overlap, you cannot guarantee you can get the same original values out after doing the swap.

Two ways to deal with this problem:

• Document that your function is lossy, and that you cannot guarantee that you will be able to extract the swapped bits back out.
  I don't like this idea, because I don't know what I'd use such an algorithm for
• Throw an exception if an overlap is fed into the algorithm, and write your program that uses this algorithm in such a way that it doesn't generate overlaps.

Answer 2

In Java you could check needed bit using:

boolean isSet(byte number, int index) {
    return (number & (1 << index)) != 0;
}

To construct new byte you could use: Byte.valueOf(string, radix)

Also, when you work with non-byte numbers, you can change byte order using ByteBuffer (ByteOrder.LITTLE_ENDIAN / ByteOrder.BIG_ENDIAN)