Algorithms, C#, Uncategorized

Bit manipulation to the rescue in C#. Reducing Space/Time complexity using Bit Manipulation


Bit manipulation is fun and still  relevant in the realm of C#. You can do things in a way that can increase performance substantially or simplify an algorithm in hand.

Bit manipulation also in certain scenarios helps to save memory, take for example if you want to store multiple flags (True/False values) the most obvious solution would be to use a list of bool types. This may seem to be OK but takes 1 byte per flag. If you are working with 30 flags in hand, you can use an Int32 type in .Net and use its bit values to store 1 for truthy values and 0 for falsy values (often referred as using  bits of an Integer to represent a Set)

So although it’s not imperative to know Bit Manipulation but it can really come to rescue in some corner cases as we plan to see in this blog post.


Bitwise Operators

Before diving deep into scenarios where Bit manipulation can come to rescue let’s look into various Bitwise operators so that we all start on the same page:

 NOTE: I am using 8 bits to explain the concepts.

The .Net int type is a  32 bit integer, but the concepts would remain the same 

Bitwise Compliment
/*Bitwise Compliment
             * 1  = 00000001
             * ~1 = 11111110 (In 2's compliment representation this is -2) 
             * ------Explanation of -2:---------
             *  2 = 00000010
             * -2 = 11111101 +1 = 11111110
Bitwise And / Set Intersection

            /*Bitwise And 
             * 1  = 00000001
             * 2  = 00000010
             * 1&2= 00000000 = 0
            Console.WriteLine(1 & 2);
Bitwise Or / Set Union
            //Bitwise Or
            //1  = 00000001
            //2  = 00000010
            //1|2= 00000011 = 3
            Console.WriteLine(1 | 2);
Bitwise XOR
               Here's how XOR works:
             * If both operands have a bit set i.e. 1, the result does not 
             * have that bit set.
             * If neither has a bit set, the result still does not have
             * the bit set. 
             * But if one has the bit set, the result is set.
             * XOR is used for checking bit parity
            //Bitwise XOR
            //1  = 00000001
            //2  = 00000010
            //1&2= 00000011 = 3
            Console.WriteLine(1 ^ 2);
Bitwise Shift Operators
One common use of shifting is to access a particular bit, for example, 
1 << a is a binary number with bit a set and the others clear(bits are 
always counted from the least significant bit, which is numbered 0)
Bitwise Right Shift

            //Bitwise Right Shift. Right shift is equivalent to division by 2
            //1   = 00000001
            //1>>2= 00000000 = 0
            Console.WriteLine(1 >> 2);
Bitwise Left Shift
            //Bitwise Left Shift . Left shift is equivalent to multiplying by 2
            //1   = 00000001
            //1<<2= 00000100 = 4
            Console.WriteLine(1 << 2);
Flag Enums
            // Bitwise OR operator is used for adding a flag to the Enum
            States states = States.AL | States.TN;
            states |= States.MN;
            states |= States.WI;
            // Bitwise ^ operator is used for removing a flag from the Enum
            states ^= States.AL;
         private static void CheckStates(States states)
            switch (states)
                case States.AL:
                case States.AL | States.TN:
                        Console.WriteLine("AL, TN");
                case States.AL | States.MN:
                        Console.WriteLine("AL, MN");

Set Subtraction

// Set Subtraction
Console.WriteLine(a & ~b);

Set subtraction can be easily understood by using a diagram:

Set Subtraction

Set Subtraction


Set Negation

// Set Negation
           Console.WriteLine(ALLBITS ^ a);

Here ALLBITS is an integer value, wherein all bits are 1


Set Bit

In order to set a bit, use the following:

// Set Bit
            a |= 1 << shift;

Clear Bit

// Clear Bit
           a &= ~(1 << shift);


Now let us look into a few problems wherein we can

leverage Bit manipulations to Reduce Complexity of

an Algorithm/ Reduce space requirements of a program.


Scenario 1: Reducing Time Complexity

Given two Integers, find whether they are of opposite signs or not.

Here is the obvious solution:


public static bool AreIntegersOfOppositeSigns(int a, int b)
           if (a > 0 && b < 0)
               return true;
           if (a < 0 && b > 0)
               return true;
           return false;

And here is the solution which uses Bit manipulation:

public static bool AreIntegersOfOppositeSignsUsingBitManipulation(int a, int b)
           return (a^b) < 0;

Did you notice the no. Of lines getting reduced? But it’s not just the lines getting reduced, it’s the complexity/

branching which got reduced here.

First solution has 3 branches/paths and 9 operators whereas the 2nd solution has no branching, additionally just 3 operators.


Scenario 2: Reducing Space Complexity

Given a String, determine if all of its characters are Unique

Here is one of the solutions wherein we use a Char Array of size 256 (assuming dealing with ASCII) as a HashTable

to figure out if there are any duplicates:


public static bool AreUniqueChars(String str)
         var chars = new bool[256];
         for (int i = 0; i < str.Length; i++)
             int val = str[i];
             if (chars[val]) return false;
             chars[val] = true;
         return true;

public static bool AreUniqueCharsUsingBitManipulation(String str)
       int checker = 0;
       for (int i = 0; i < str.Length; ++i)
           int val = str[i] - 'a';
           if ((checker & (1 << val)) > 0) return false;
           checker |= (1 << val);
       return true;

In this scenario we got rid of the Character array that we were using as a HashTable to detect duplicates.

Final Words

We saw two specific scenarios to reduce Space and Time complexity of an Algorithm. I hope you got the idea of the

power of Bit Manipulation and how can we use it to write performant and efficient code.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s