Why
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
*/
Console.WriteLine(~1);
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;
CheckStates(states);
states |= States.MN;
CheckStates(states);
states |= States.WI;
CheckStates(states);
// Bitwise ^ operator is used for removing a flag from the Enum
states ^= States.AL;
CheckStates(states);
}
private static void CheckStates(States states)
{
switch (states)
{
case States.AL:
{
Console.WriteLine("AL");
}
break;
case States.AL | States.TN:
{
Console.WriteLine("AL, TN");
}
break;
case States.AL | States.MN:
{
Console.WriteLine("AL, MN");
}
break;
}
}
Set Subtraction
// Set Subtraction
Console.WriteLine(a & ~b);
Set subtraction can be easily understood by using a diagram:
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.
Saurabh nijhawan's weblog 