Mastering Bit-Manipulation : A Beginner to expert guide with simple Examples

Bit Manipulation is one of the most efficient way to optimize your code . Whether you are working with algorithms ,Cryptography or System level programming ,understanding of bit-manipulation can give you a significant performance boost .In this guide we will break down bit manipulation into very basic to advance technique using simple examples which anyone can be able to understand .

What is Bit-Manipulation ?

Bit-Manipulation refers to act of algorithmically altering the individual bits within a binary number. Since all the data are stored in a computer as binary bits (0’s and 1’s) if we get a control over the bits directly then our code will be much efficient in both in terms of performance and memory usage.

Example :

Let’s take the number 7 as binary :

Decimal : 7
Binary : 0111

Each number is stored as a series of bits ,where each bit is either 0 or 1. Bit-manipulation works on this binary representation using bitwise operator to achieve efficient results.

Why Bit-Manipulation ?

Bit manipulation is important for several reasons:

• Efficiency: Bitwise operations are incredibly fast and can be used to replace complex mathematical operations.

• Memory Optimization: Using bits allows you to pack more information into smaller memory spaces, which is crucial in embedded systems and performance-critical applications.

• Low-Level Programming: Bit manipulation gives you fine-grained control over hardware-level operations.

“Bit manipulation is like a cheat code for programmers. Once you learn it, the possibilities are endless.”

Basics Of Bitwise Operator :

Bitwise Operator allow us to directly manipulate over the bits of a number. Let's dive deep into the six most used operator :

1. AND (&) :

The AND operator compares two bits and return 1 if two bits are 1 ,otherwise return 0.

int a=5; // binary value 0101
int b=3; //binary value 0011
int result= a & b; // the answer will be 0001 
System.out.println(result);

In the above example the value of result is 1 because if we will operate 0101 and 0011 in binary in case of last bit both the value contains 1 and rest of the bit of two numbers doesn't contain 1 in case both bits(0 & 1 , 1 & 0 , 0 & 0). So the result will be 0001.

2. OR ( | ) :

The OR operator returns 1 of any of the bits is 1 otherwise it will return 0 .

int a =5; //binary value is 0101
int b =3; // binary value is 0011
int result =a | b; //result will be 0111 (7 in decimal)

I'm above example the value of result is 0111 because of operator returns 1 if any of the bits is 1 .So it is 0111 (7 in decimal)

3. XOR ( ^ ) :

The XOR (Exclusive OR) operator returns 1 if both bits are different and returns 0 if both bits are same.

int a =5; //binary value 0101
int b=3; // binary value is 0011
int result =a ^ b; //result will be 0110

In the above example the result will be 6 in decimal because in case of similar bits it return 0 and in case of different bits it return 1. Here in case if bit in a is 0 and bit in b is 1 or bit is a is 1 and bit in b is 0 then it will return 1 . If both the bits like both the a and b contains 0 or 1 then it returns 0. So the result will be 0110 which is 6 in decimal.

4. NOT ( ~ ) :

The NOT operator flips all the bits. `1` becomes `0`, and `0` becomes `1`.

int a =5; //binary value 0101
int result= ~a ; // result will be 1010

5. Left Shift Operator :( << )

Left Shift operator Shift the bits of a number to left by filling 0’s in the right side.

int a=5; //binary value of 5 is 0101
int result=a<<1; //means we will shift all the bits of 5 1 times
//Result will be 1010 as it is 10 in deciaml

In the above example the binary representation of 5 is 0101 and when we are left shifting it’s bits 1 time the left most bit of the 0101 is 0 and next 1 and 0 and 1. So After left shift the value will become 01010 so one 0 is added in the right hand side and the bits shift to the left by 1.

6. Right Shift Operator ( >> ):

Right Shift operator Shifts the bits of a number to the right side by removing the right most bit of the number.

int a =7; //binary representation of 7 is 0111
int res=a>>1;
System.out.println(res); //result will be 3 as the right most 1 will be removed so 0111 will become 0011
//the value of 0011 is 3
//Similarly if we will shift it 2 times then it will become 1

Some Tips Which makes Bit-Manipulation Easy :

1. If we perform & operation between any number and 0 it will always become 0.

2. If we perform & operation between any number and 1 we will get that number . Because the & operation returns true if both the bits are 1 and returns 0 if both the bits are not 0.

Ex. 1110001 & 1111111 =1110001

It means if we AND(&) all bits of a number with 1 then it will return the number itself.

3. If we perform OR operation between any number with 0 then we will get that number itself.

4. If we perform OR operation between any number with 1 then it will give it’s next number.

5. If we perform AND( & ) operation ,OR( | ) operation with any number itself it will return the number itself ( a & a=a ,a | a=a ) but if we Perform XOR operation with a number and itself it will return 0 (a^ a=0).

Let’s Solve some Question to Understand it in more Details :

Q1 . Check Whether the number is even or Odd ?

To solve this question without bit-wise operator what we will do is we have to divide the number with 2 and check whether the reminder is 0 or 1 .So using bit wise operator also we have to check same thing . We know the right most bit of a number adds 0 or 1 with a number. So if the right most bit is 1 then the number is odd and if the right most bit of a number is 0 then it is even .

Now we got some idea about the logic . So What we will do now is we will perform AND operation between the number and 1 which will give us the value of the right most bit of the number .

Let’s code it :

int num=12;//binary representation of the number 12 is 1100 
//so the right most bit is 0 and the number is even 
//if we try with 13 which binary representation is 1101 and the right most bit is 1
// so 13 is odd
if(num &1 ==0){
System.out.println("Number is even");
}else{
System.out.println("Number is Odd");
}

Q2. Swap two variables without using the third variable .

We all know about swapping of two numbers but we were doing that using a third variable. But here we can swap two numbers without the third variable using bitwise operators.

int a=5; //binary representation of 5 is 0101
int b=3;//binary representation of 3 is 0011
//to swap two numbers we will use XOR operator 
//first we will store the value of a^b in a and then the value of a^b in b
//then again update the value if a with a^b
System.out.println("Before swapping value of a : "+a+" and b : "+b);
a=a^b;
b=a^b;
a=a^b;
System.out.println("After swapping value of a : "+a+" and b : "+b);

We can solve many problems using bit manipulation. To find more questions, you can check coding platforms like LeetCode, GeeksforGeeks, and many others, or simply Google them.

Now let's dive a bit deeper into bit manipulation. We have solved some simple problems, but we can also tackle more complex problems using bit manipulation. Suppose we are given a complex scenario where we cannot apply bitwise operators or simple formulas. What do we do then? We can use bit masking, which will help us solve complex problems.

What is Bit-Masking ?

Bit-masking is a technique through which we will create masks using bits to access or manipulate a specific bit of a number. A mask is a pattern which will be generated using bits and will be applied to any number to manipulate specific bit. For example we are given a number and we need to find out whether the specific bit of a number is set bit or not. So in that case we will create a mask using the bits and apply to that number using bitwise operator to find the specific bit is set bit or not. Set bit basically is a bit represented by 1.

int a =5; // binary representation of 5 is 0101
//suppose we have to find the 3rd bit is a set bit or not
//in that case we have to create a mask
int mask=1<<2; 
//as we know if we use & operator for any number with 1 then we will get 1
//because & operator returns 1 if and only if both the bits are 1
//So here we have to calculate the set bit which is 1 and we have to check for 3rd bit
//so if we will use left-shift operator for 1 then it will become 100 and we can perform & operation 
//between the number and the mask to get whether the 3 rd bit is set bit or not
if(a & mask ==1){
System.out.println("3rd bit is a set bit");
}else{
System.out.println("3rd bit is not a set bit");
}

Let’s understand this with another example.

Suppose we are given a number and we need to flip its nth bit. Flipping means changing the bit from 0 to 1 or from 1 to 0.

To solve this problem, we need to create a mask for the nth bit and perform an XOR operation between the number and the mask. This will flip the nth bit.

int a=5; //binary representation of 5 is 0101
int mask=1<<2; //binary representation if 1 is 0001 and we will left shift 
//1 two times . so it will become 100
//now we can XOR a and mask to flip our 3rd bit
int result=a^mask;

Real-World Application of Bit-Manipulation :

Bit manipulation is used in many fields to provide more granular control over bits. Let’s discuss them one by one:

1. Cryptography: Bit manipulation is essential in encryption algorithms that operate at the bit level.

2. Graphics Processing: GPUs use bit manipulation to manage pixels and colors in images.

3. Networking: Protocols like IPv4 and IPv6 rely on bitwise operations to manage data packets.

4. Embedded Systems: Low-level programming with microcontrollers often requires working directly with bits.

Here is a saying :

Understanding bits unlocks the true power of computing—it's the difference between writing code and crafting solutions.

Conclusion :

Bit manipulation is an invaluable tool that allows programmers to work efficiently at the binary level. Mastering these techniques will not only improve your problem-solving skills but also open up new ways to optimize your code for speed and memory. Whether you're optimizing algorithms or working with low-level hardware, bit manipulation is a skill that every programmer should have in their toolbox.

Bits are the foundation of everything in computing. Master them, and you master the machine.

I hope you now have a better understanding of how bit manipulation works. Please explore this topic further for a deeper understanding. If you have any suggestions for improvement or any questions, feel free to leave a comment or message me on LinkedIn. Let's take a step forward in our coding journey. Happy coding!!