Bit exchange operation

Question

I have been working on a certain task these days and after several hours of torture, I have done it! However, I believe the code that I have "crafted" is quite difficult to be understood and to be honest, I wouldn't be able to understand it if I wasn't the one who made it. Anyways, this is my code. I would like to receive some advice about what I could do to make it a little bit more simple and, by any chance, shorter:

 using System;
 class BitExchangeAdvanced
  {
    static void Main()
{
    int  num1, num2,  p, q, k, loop;
    uint n, n1, bit;
    while (true)
    {
     // input number

        Console.WriteLine("Input n:");
        if (uint.TryParse(Console.ReadLine(), out n))
        {
            if (n >= 0)
            {
                break;
            }
        }
    }

    // input first position
    while (true)
    {
        Console.WriteLine("Input p:");
        if (int.TryParse(Console.ReadLine(), out p))
        {
            if (p >= 0)
            {
                break;
            }
        }
    }

    // input second position

    while (true)
    {
        Console.WriteLine("Input q:");
        if (int.TryParse(Console.ReadLine(), out q))
        {
            if (q >= 0)
            {
                break;
            }
        }
    }

    // input the limit
    while (true)
    {
        Console.WriteLine("Input k:");
        if (int.TryParse(Console.ReadLine(), out k))
        {
            if (k > 0)
            {
                break;
            }
        }
    }

        // check which position is first
    if (p>q)
    {
        num1 = q;
        num2 = p;
    }
    else
    {
        num1 = p;
        num2 = q;
    }

        // the loop is used in the "for" loop
    loop = num1;

        // check if the inpputs are valid for completing the operation
    if (num2 - num1 < k || num1 + k > 32 || num2 + k > 32)
    {
        Console.WriteLine("Overlapping or out of range");
    }
    else
    {

        // use "for" in order to complete the formula {p, p+1, …, p+k-1}
        for (num1 = loop; num1 < (loop + k); num1++)
        {
                bit = (n >> num1) & 1; // check the first value
                if (bit == 1)
                {
                    n1 = (bit << num1 + (num2 - num1)) | n; // input the value to its analog in num2
                    bit = (n >> num1 + (num2 - num1)) & 1; // complete the opposite operation
                    if (bit == 1)
                    {
                        n1 = (bit << num1) | n1;
                    }
                    else
                    {
                        n1 = ~((bit + 1) << num1) & n1;
                    }
                }
                else
                {
                    n1 = ~((bit + 1) << num1 + (num2 - num1)) & n; // same as the above but with different operations
                    bit = (n >> num1 + (num2 - num1)) & 1; // complete the opposite operation again
                    if (bit == 1)
                    {
                        n1 = (bit << num1) | n1;
                    }
                    else
                    {
                        n1 = ~((bit + 1) << num1) & n1;
                    }
                }
                n = n1;
                num2 = num2 + 1; // completes the second formula {q, q+1, …, q+k-1}
        }

        Console.WriteLine("The result is: {0}", n); // print the result
    }



  }
 }

The task is: Write a program that exchanges bits {p, p+1, …, p+k-1} with bits {q, q+1, …,q+k-1} of a given 32-bit unsigned integer. The first and the second sequence of bits may not overlap.

Answer 1

I think this is suggesting roughly (maybe exactly) the same technique as @harold does in his answer, but I'm not entirely certain that I understand his answer, so I can't say with certainty whether it's the same or not.

I'd consider two facts in coming to an answer. First, that where two bits are identical, we don't need to do anything to swap them--i.e., swapping a 1 with a 1 or a 0 with a 0 doesn't change anything.

Therefore, we only need to do anything where the bits are not equal to each other. In this case, we have to flip both bits--i.e., the one that was a 0 has to become a 1, and the one that was a 1 has to become a 0.

At least to me, that immediately brings an exclusive-or to mind. An exclusive-or produces a 1 if one input or the other (but not both) is a 1. Looking at it slightly differently, it produces a 1 if the bits are not equal to each other, and a 0 if they are equal to each other. Looked at from yet a slightly different angle, an XOR with 0 leaves a bit unchanged, and an XOR with 1 always flips the bit (changes a 0 to a 1, or a 1 to a 0).

With that in hand, the job becomes fairly simple: we start by XORing the bits in the two ranges. This gives us 0s where they contain identical bits (meaning we want to leave them unchanged). It gives us 1s where they contain differing bits (meaning we want to flip the bits in both ranges).

We then XOR that mask with the bits in each range. That leaves the bits in each range unchanged where they were identical to start with, and flips the bits in each range where they were different.

For example, let's consider swapping the first 4 bits of a byte with the second 4 bits:

first four: 0 1 0 1
last four:  0 1 1 0

When we XOR these, we get:

mask:       0 0 1 1

We then XOR that back with each of the input ranges:

first four: 0 1 0 1
mask:       0 0 1 1
result:     0 1 1 0

last four: 0 1 1 0
mask:      0 0 1 1 
result:    0 1 0 1

And now the first four have the same values as the last four did to start with (and vice versa).

Looking more specifically at your code, it has a fair number of places I think it could be made simpler and probably shorter. You start by reading four numbers, each with a block of code like this:

while (true)
{
 // input number

    Console.WriteLine("Input n:");
    if (uint.TryParse(Console.ReadLine(), out n))
    {
        if (n >= 0)
        {
            break;
        }
    }
}

The only things that change from one of these to the next are the string you display and the identity of the variable you're reading. This is an ideal candidate for being turned into a function. The function needs to read a number (just as you've done it above) and return the value when it's successful. Then the code in main will just call that function for each of the numbers it needs to read:

n = read_number("Input n:");
p = read_number("Input p:");
q = read_number("Input q:");
k = read_number("Input k:");

It's probably possible to avoid having to pass the string as well--you'd pass the variable itself, and figure out the name of that variable using reflection to build your string. That takes some rather more advanced use of .NET though, and I wouldn't advise it for now.

When it comes to finding which range is first:

if (p>q)
{
    num1 = q;
    num2 = p;
}
else
{
    num1 = p;
    num2 = q;
}

I think I'd just use p and q, but swap them if they're out of order:

if (p>q) {
    temp = p;
    p = q;
    q = temp;
}

(...and wish you were using C++, so you didn't have to re-implement basic operations like this for the 4 billionth time).

I've already advised a complete rewrite of the swapping code itself, so I guess there's not much point in reviewing that part of your code.

Answer 2

I tried to answer when this question was on SO, but you removed and reposted it here.. so here's a non-code-review. This is not a comment on your code, but a suggestion for an entirely different approach.

That's much more complicated then it has to be.

Look into delta swaps. delta(x, m, d) takes an input x, a mask m and a distance d (the delta), and swaps non-overlapping pairs of bits such that one of the pair is indicated by the mask and the other of the pair is d places towards the most significant bit.

It sounds more complicated than it is: (this is pseudo code, and not tested, you can look up the real definition in The Art of Computer Programming 4A, Bitwise tricks and techniques)

delta(x, m, d) =
    let temp = x ^ ((x >> d) & m)
    in x ^ temp ^ (temp << d)

If you recast your problem in terms of delta, the only trouble is getting the mask and the distance. The distance is just abs(p - q). Generating a mask from some position to an other is a common problem (it has been asked on SO several times) and not too hard.

Answer 3

int  num1, num2,  p, q, k, loop;
uint n, n1, bit;

You shouldn't declare all your variables in one place. Declare them where they're first used.

Also, the names are quite confusing. You're not trying to save bytes, you're trying to write understandable program, so avoid names that don't say anything about the variable, instead use descriptive names.

For example, based on a comment later, you could use firstPosition or position1 instead of p.

---

while (true)
{
    Console.WriteLine("Input p:");
    if (int.TryParse(Console.ReadLine(), out p))
    {
        if (p >= 0)
        {
            break;
        }
    }
}

This same code is repeated several times almost verbatim. You should try to avoid that (it's called Don't Repeat Yourself, or DRY for short) and instead write a method to encapsulate this. For example:

public static int ReadInt(string name)
{
    int value;

    while (true)
    {
        Console.WriteLine("Input p:");
        if (int.TryParse(Console.ReadLine(), out value) && value >= 0)
            return value;
    }
}

Also, I'm confused about your usage of int and uint: Why do you use both, but sometimes use int for numbers that cannot be negative?