Category Archives: Logical

Swapping 2 numbers patterns / algorithms

  Swapping 2 numbers with temporary variable


static void Swap2NumbersWithTempVariable()

{

int firstNumber = 111;

int secondNumber = 222;

int temp;

Console.WriteLine(“================”);

Console.WriteLine(“First Number:” + firstNumber);

Console.WriteLine(“Second Number:” + secondNumber);

temp = firstNumber;

firstNumber = secondNumber;

secondNumber = temp;

Console.WriteLine(“First Number:” + firstNumber);

Console.WriteLine(“Second Number:” + secondNumber);

Console.WriteLine(“================”);

}

Swapping 2 numbers without temporary variable

static void Swap2NumbersWithOutTempVariable()

{

int firstNumber = 111;

int secondNumber = 222;

Console.WriteLine(“================”);

Console.WriteLine(“First Number:” + firstNumber);

Console.WriteLine(“Second Number:”

+ secondNumber);

firstNumber = firstNumber + secondNumber;

secondNumber = firstNumber – secondNumber;

firstNumber = firstNumber – secondNumber;

Console.WriteLine(“First Number:” + firstNumber);

Console.WriteLine(“Second Number:” + secondNumber);

Console.WriteLine(“================”);

}

Swapping 2 numbers using bitwise XOR operator

static void Swap2NumbersUsingBitWiseXOR()

{

int firstNumber = 111;

int secondNumber = 222;

Console.WriteLine(“================”);

Console.WriteLine(“First Number:” + firstNumber);

Console.WriteLine(“Second Number:” + secondNumber);

firstNumber ^= secondNumber;

secondNumber ^= firstNumber;

firstNumber ^= secondNumber;

Console.WriteLine(“First Number:” + firstNumber);

Console.WriteLine(“Second Number:” + secondNumber);

Console.WriteLine(“================”);

}
Advertisements

String Reversal Patterns/Algorithms

String Reversal with Swap algorithm – trivial one and average performance and the overhead of copying twice one to char array and other to original as strings are immutable. Extra variable is used as temp unnecessarily

    static string ReverseStringWithTemp(string sourceString)

        {

            char[] inputStream = sourceString.ToCharArray();

            for (int i = 0, j = sourceString.Length –  1; i < j; i++, j–)

            {

                char temp = inputStream[i];

                inputStream[i] = inputStream[j];

                inputStream[j] = temp;

            }

            return new string(inputStream);

        }

String Reversal with Copy to Char Array – trivial one an average performance and the overhead of copying twice one to char array and other to original as strings are immutable, no use of temp variable so memory efficient normal reversal

        static string ReverseStringWithoutTemp(string sourceString)

        {

            char[] inputStream = sourceString.ToCharArray();

            for (int i = 0, j = sourceString.Length – 1; i < j; i++, j–)

            {

                inputStream[j] = sourceString[i];

                inputStream[i] = sourceString[j];

            }

            return new string(inputStream);

        }

String Reversal with Stack – uses FILO structure for string reversal. Performance is almost equal to the normal reversals. Note that two loops are being used

        static string ReverseStringWithStack(string sourceString)

        {

            Stack<char> reverseString = new Stack<char>();

            for(int i = 0; i < sourceString.Length;i++)

            {

                reverseString.Push(sourceString[i]);

            }

            string targetString = string.Empty;

            while (reverseString.Count > 0)

            {

                targetString += reverseString.Pop();

            }

 

            return targetString;

        }

String Reversal with Bitwise XORing and quick one too without extra memory usage

        static string ReverseStringWithBitWiseXOR(string sourceString)

        {

            char[] inputStream = sourceString.ToCharArray();

 

            for (int i = 0, j = sourceString.Length – 1; i < j; i++, j–)

            {

                inputStream[i] ^= inputStream[j];

                inputStream[j] ^= inputStream[i];

                inputStream[i] ^= inputStream[j];

            }

            return new string(inputStream);

        }

In c# x1 ^= x2 equals to x1 = x1 ^ x2 where ^ is the bitwise XOR.

Let’s say we want to switch 2 binary values x1 = 100 and x2 = 111 so that x1 = 111 and x2 = 100.

XOR (Exclusive OR) table
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
First operation: x1 = x1 XOR x2
x1: 1 0 0
x2: 1 1 1
New x1: 0 1 1
Second operation x2 = x2 XOR x1
x1: 0 1 1
x2: 1 1 1
New x2: 1 0 0
Third operation: x1 = x1 XOR x2
x1: 0 1 1
x2: 1 0 0
New x1: 1 1 1

We now have x1 = 111 and x2 = 100.