Bit Manipulation and Bit Masking Concepts
Introduction-
In terms of electronic switch we can say 0 denotes an OFF switch and 1 denotes an ON switch.
In terms of magnetic domain on a hard drive, we can say 0 denotes an unmagnetized domain, and 1 denotes a magnetized domain.
Uses of bit manipulation concepts in our coding
Bit manipulation is a technique that can give programmers a significant performance advantage in certain algorithms. It can help to reduce the time complexity.
By working directly with binary data using bitwise operators, we can perform operations faster than with traditional arithmetic operations. The reason for this is simple: computers understand binary data. When we perform any operation, it gets converted into bits so that the machine can perform the operation on that binary data.
Using bit manipulation can be especially important in computation programming and competitive programming, where every millisecond can make a difference. When we're building applications that have to work in high-load environments like billing systems, live streaming, IVR systems, or other similar applications, the ability to manipulate bits directly can give us an extra edge in performance.
By optimizing code with bit manipulation, we can reduce execution time, minimize memory usage, and make our programs run more efficiently. For example, by using bitwise operators to perform multiplication and division operations, we can reduce the time it takes for the program to execute those operations. This can be especially useful in computation programming and competitive programming where speed and efficiency are critical.
Binary Representation
Binary representation is a way of representing numbers using only two digits: 0 and 1. This is also known as the base-2 number system. Computers use binary representation to store and process data because it's the most efficient way to represent data using electronic circuits.
Each digit in a binary number represents a power of 2. The rightmost digit represents 20, the next digit to the left represents 21, the next represents 22, and so on.
For example, the binary number 1011 represents:
1 * 23 + 0 * 22 + 1 * 21 + 1 * 20
= 8 + 0 + 2 + 1
= 11
To convert a decimal number to a binary number, we use a process called "dividing by 2". We repeatedly divide the decimal number by 2, writing down the remainder each time, until we reach 0. The remainders, read from bottom to top, give us the binary representation of the decimal number.
For example, to convert the decimal number 11 to binary:
11 / 2 = 5 remainder 1
5 / 2 = 2 remainder 1
2 / 2 = 1 remainder 0
1 / 2 = 0 remainder 1
Binary representation: 1011 (writing remainder from bottom to top)
Bitwise Operations
Bitwise operations are a set of operations that work on individual bits in a binary number. These operations are used to manipulate and modify binary data.
There are six bitwise operators:
Bitwise AND (&)
Bitwise OR (|)
Bitwise XOR (^)
Bitwise NOT (~)
Left shift (<<)
Right shift (>>)
What is the meaning of bit is set or, bit is unset?
When we says the bit is set it means the value is 1. Similarly the bit is unset means the value is 0.
3-Key points:
In AND(&) operations the bit is set only if both bit is 1 otherwise it is unset.
In OR(|) operations the bit is unset only if both bit is 0 otherwise it is set.
In XOR(^) operations the bit is set only if both a and b bits are not same.
(Trick : In AND the we can get result by multiplication and in OR by addition)
Bitwise AND (&) operator
The bitwise AND operator returns a 1 in each bit position where both operands have a 1. Otherwise, it returns a 0.
Example:
int a = 10; // binary representation of 10 is 1010
int b = 6; // binary representation of 6 is 0110
int c = a & b; // c will be 2 (binary 0010)
Bitwise OR (|) operator
The bitwise OR operator returns a 1 in each bit position where either or both operands have a 1. Otherwise, it returns a 0.
Example:
int a = 10; // binary representation of 10 is 1010
int b = 6; // binary representation of 6 is 0110
int c = a | b; // c will be 14 (binary 1110)
Bitwise XOR (^) operator
The bitwise XOR operator returns a 1 in each bit position where only one of the operands has a 1. Otherwise, it returns a 0.
Example:
int a = 10; // binary representation of 10 is 1010
int b = 6; // binary representation of 6 is 0110
int c = a ^ b; // c will be 12 (binary 1100)
Bitwise NOT (~) operator
The bitwise NOT operator is a unary operator that inverts all the bits of its operand. It returns a 1 for each bit position where the corresponding bit of the operand is 0, and vice versa.
Example:
Note: Here 1010 can be written as 0000…00001010 that is 28 times 0 before 1010 to made digit count 32. Because to store 1010 it actually tooks 32 bit of memory at least.
int a = 10; // binary representation of 10 is 1010
int b = ~a; // b will be -11 (binary 11111111111111111111111111110101)
Left shift (<<) operator
The left shift operator shifts the bits to left side. The vacant positions on the right are filled with zeros.
Example:
int a = 10; // binary representation of 10 is 1010
int b = a << 2; // b will be 40 (binary 101000)
Number a is 1010. a << 2 means shift 1010 to left by 2 times.
Right shift (>>) operator
As we see above left shift, shifts the bits to left side. In the same way the right shift operator shifts the bits to right side. The vacant positions on the left are filled with the sign bit (for signed data types) or with zeros (for unsigned data types).
Example:
int a = 5; // binary representation of 5 is 101
int b = a >> 1; // b will be 2 (binary representation of 2 is 010)
Bitwise Tricks and Techniques
Get bit
We will learn how to obtain the bit value of a specific position in a binary number. Let's take the decimal number 5 as an example, which is equivalent to the binary number 101. From this binary representation, we can see that the first position contains 1, the second position contains 0, and the third position contains
To determine the bit value at a particular position, we need to use bitwise operations such as AND, OR, NOT, or bit shifting.
For instance, to obtain the bit value at the first position, we can perform a bitwise AND operation between the number and a binary number that has all zeros except for a 1 in the first position (i.e., 001).
If we apply this operation to the number 101, we get the result:
(101 & 001) = 001
The result of this operation is a non-zero number, indicating that the bit value at the first position in the decimal number 5 is 1.
Similarly, to obtain the bit value at the third position, we need to perform a bitwise AND operation with a binary number that has all zeros except for a 1 in the third position (i.e., 100).
If we apply this operation to the number 101, we get the result:
(101 & 100) = 100
Again, the result is a non-zero number, indicating that the bit value at the third position in the decimal number 5 is 1.
We can use this approach to calculate the bit value at any position in a binary number. To do so, we need to perform a bitwise AND operation between the number and a binary number that has all zeros except for a 1 in the desired position.
Now, the next task is to locate the binary number with only one bit set to 1 in the desired position, while the rest are 0s.
In the example mentioned earlier, 001, 010, and 100 correspond to the binary numbers for the 1st, 2nd, and 3rd positions, respectively. These binary numbers are referred to as masked numbers and can be obtained using bit masking technique.
Bit Masking
Bit masking is a technique used in computer programming to manipulate individual bits of a binary number. It involves using a mask, which is a binary number with one or more bits set to 1, to select or clear specific bits in a binary number.
To get the bit mask here we need to left shift 1 by (i-1) times, where “i” is position on which we want to get the bit.
For example, To get the masked binary number to get the 1st position we have to shift 1 by (1-1) that is 0 times, because here i value is 1.
So the masked binary number for 1st position is:
001<<(i-1), here i=1.
Thus, 001<< 0 = 001
Masked binary number for 2nd position is:
001<<(i-1), here i=2.
Thus, 001<<1 = 010
Masked binary number for 3rd position is:
001<<(i-1), here i=3.
Thus, 001<<2 = 100
Set bit
In addition to getting the bit value at a specific position, we can also set a bit at a particular position in a binary number using bit masking.
To set a bit at a particular position, we need to perform a bitwise OR operation between the number and a binary number that has all zeros except for a 1 in the desired position.
For example, to set the bit at the third position in the decimal number 5, we can perform a bitwise OR operation with a binary number that has all zeros except for a 1 in the third position (i.e., 100):
(101 | 100) = 101
After performing this operation, the bit at the third position in the decimal number 5 will be set to 1.
We can use the following code:
int bitPosition = 3;
int mask = 1 << bitPosition;
x = x | mask;
Here, bitPosition represents the position of the bit we want to set, which is 3 in this case. We left shift 1 by the bitPosition to create the mask, which will have a 1 in the 3rd position and 0s in all other positions.
The | operator performs a bitwise OR operation between the original value of x and the mask. This will set the 3rd bit of x to 1, without affecting any of the other bits.
We can generalize this code to set any bit position by changing the value of bitPosition:
int bitPosition = // set this to the desired bit position
int mask = 1 << bitPosition;
x = x | mask;
Note that if the bit at the specified position is already set, this operation will have no effect on that bit.
Clear bit
Similar to setting a bit at a particular position, we can also clear a bit at a particular position in a binary number using bit masking.
To clear a bit at a particular position, we need to perform a bitwise AND operation between the number and a binary number that has all ones except for a 0 in the desired position.
For example, to clear the bit at the third position in the decimal number 5, we can perform a bitwise AND operation with a binary number that has all ones except for a 0 in the third position (i.e., 011):
(101 & 011) = 001
After performing this operation, the bit at the third position in the decimal number 5 will be cleared (i.e., set to 0).
We can use the following code to clear a bit at a specific position:
int bitPosition = 3;
int mask = ~(1 << bitPosition);
x = x & mask;
Here, bitPosition represents the position of the bit we want to clear, which is 3 in this case. We left shift 1 by the bitPosition to create the mask, which will have a 1 in the 3rd position and 0s in all other positions. We then perform a bitwise NOT operation on the mask to create a new mask with 1s in all positions except for the 3rd position.
The & operator performs a bitwise AND operation between the original value of x and the new mask. This will clear the 3rd bit of x to 0, without affecting any of the other bits.
Note that if the bit at the specified position is already clear, this operation will have no effect on that bit.
Update bit
In addition to setting and clearing individual bits in a binary number, we may also need to update or change the value of a specific bit to either 0 or 1.
To update a bit at a particular position, we can first clear the bit using a bitwise AND operation, and then set it to the desired value using a bitwise OR operation.
For example, to update the bit at the third position in the decimal number 5 to 1, we can first clear the bit using a bitwise AND operation with a binary number that has all ones except for a 1 in the third position (i.e., 1011):
(101 & 1011) = 001
After this operation, the bit at the third position in the decimal number 5 is cleared (i.e., set to 0).
We can then set the bit to 1 using a bitwise OR operation with a binary number that has all zeros except for a 1 in the third position (i.e., 100):
(001 | 100) = 101
After this operation, the bit at the third position in the decimal number 5 is updated to 1.
We can use the following code to update a bit at a specific position:
int bitPosition = 3;
int clearMask = ~(1 << bitPosition);
int setMask = 1 << bitPosition;
x = (x & clearMask) | setMask;
Here, bitPosition represents the position of the bit we want to update, which is 3 in this case. We left shift 1 by the bitPosition to create the setMask, which will have a 1 in the 3rd position and 0s in all other positions. We then perform a bitwise NOT operation on the setMask to create the clearMask with 1s in all positions except for the 3rd position.
The & operator performs a bitwise AND operation between the original value of x and the clearMask. This will clear the 3rd bit of x to 0, without affecting any of the other bits.
We then perform a bitwise OR operation between the result of the previous operation and the setMask. This will set the 3rd bit of x to 1, without affecting any of the other bits.
We can generalize this code to update any bit position by changing the value of bitPosition:
int bitPosition = // set this to the desired bit position
int clearMask = ~(1 << bit_position);
int setMask = 1 << bit_position;
x = (x & clearMask) | setMask;
Note that this operation will update the bit to the desired value, regardless of whether it was previously set to 0 or 1.
Swapping values without using third variable
In some programming problems, we may need to swap the values of two variables without using a third variable. This can be achieved by using bitwise operators.
To swap two values x and y, we can perform the following bitwise operations:
Set x to the XOR of x and y.
Set y to the XOR of x and y.
Set x to the XOR of x and y.
This works because the XOR operator returns a 1 in each bit position where the corresponding bits of either but not both operands are 1. By performing the XOR operations as described above, the original values of x and y are swapped without using a third variable.
We can use the following code to swap the values of two variables x and y:
int x = 5;
int y = 7;
x = x ^ y;
y = x ^ y;
x = x ^ y;
System.out.println("x = " + x + ", y = " + y);
In this example, we first set x to the XOR of x and y. The value of x is now the result of the XOR operation between the original values of x and y.
Next, we set y to the XOR of x and y. Since x now has the value of the original y, the result of the XOR operation between x and y is the original value of x. Thus, y is now set to the original value of x.
Finally, we set x to the XOR of x and y. At this point, y has the original value of x and x has the original value of y, so the result of the XOR operation between x and y is the original value of y. Thus, x is now set to the original value of y.
After these operations, the values of x and y have been swapped without using a third variable.
Note that this method only works for variables that can be represented in binary form, such as integers. It may not be applicable to other types of variables. Additionally, this method can be less efficient than using a third variable, particularly for large values of x and y.
Bit Manipulation in Algorithms
Bit manipulation is a powerful technique that can be used to optimize the performance of certain algorithms and reduce memory usage. It is an essential skill for low-level programming and can be a valuable tool for solving a wide range of problems.
Bit manipulation in bitwise algorithms
Bitwise algorithms involve manipulating individual bits within a binary number to perform operations like bitwise AND, OR, XOR, and shifting. Bit manipulation can be used to optimize the performance of these operations in a variety of applications, including data compression, cryptography, and error detection and correction.
For example, in data compression algorithms like Huffman coding, bit manipulation can be used to represent the frequency of characters in a compressed file using the minimum number of bits possible. This can greatly reduce the size of the compressed file and improve performance.
Bit manipulation in dynamic programming
Dynamic programming is a technique used to solve optimization problems by breaking them down into smaller subproblems and using the solutions to these subproblems to solve the original problem. Bit manipulation can be used to optimize the storage of solutions to these subproblems, reducing memory usage and improving performance.
For example, in the Knapsack problem, a dynamic programming approach can be used to determine the maximum value that can be obtained by selecting items with given weights and values, subject to a weight limit. Bit manipulation can be used to store the solutions to subproblems in a bit vector, reducing the memory required to store the solutions.
Bit manipulation in graph algorithms
Graph algorithms involve working with graphs, which are collections of nodes and edges. Bit manipulation can be used to optimize the representation and traversal of graphs, reducing memory usage and improving performance.
For example, in the Dijkstra's algorithm, which is used to find the shortest path between two nodes in a graph, bit manipulation can be used to represent the set of unvisited nodes as a bit vector, reducing the memory required to store the set.
Bitsets
Bitsets are a data structure in computer programming that are used to represent sets of bits, allowing for efficient manipulation of binary data. In this post, we will discuss the definition and implementation of bitsets in Java, their basic operations, and some of their applications in solving problems.
Definition and implementation
In Java, the BitSet class provides a built-in implementation of bitsets. A BitSet is a fixed-size array of bits that can be used to represent a set of integers or other binary data. The size of a BitSet is determined at construction time, and each bit in the BitSet can be accessed using the get() and set() methods. The BitSet class also provides a variety of useful methods for manipulating bitsets, including bitwise operators like AND, OR, XOR, and NOT, as well as methods for setting and clearing individual bits.
Here's an example of how to create and use a BitSet in Java:
package codeKatha.dsa;
import java.util.BitSet;
public class BitSetExample {
public static void main(String[] args) {
BitSet bitSet = new BitSet(8); // create a BitSet with 8 bits
bitSet.set(0); // set the first bit
bitSet.set(3); // set the fourth bit
bitSet.set(7); // set the eighth bit
System.out.println(bitSet); // prints "{0, 3, 7}"
}
}
In this example, we create a BitSet with 8 bits using the constructor new BitSet(8). We then set the first, fourth, and eighth bits using the set() method, and print the contents of the BitSet using the toString() method.
Basic operations on bitsets
The basic operations on bitsets include setting and clearing individual bits, as well as performing bitwise operations like AND, OR, XOR, and NOT. Here's an example of how to perform these operations in Java:
package codeKatha.dsa;
import java.util.BitSet;
public class BitSetOperationsExample {
public static void main(String[] args) {
BitSet bitSet1 = new BitSet(8);
BitSet bitSet2 = new BitSet(8);
bitSet1.set(0);
bitSet1.set(3);
bitSet1.set(7);
bitSet2.set(1);
bitSet2.set(3);
bitSet2.set(5);
BitSet andResult = (BitSet) bitSet1.clone();
andResult.and(bitSet2);
BitSet orResult = (BitSet) bitSet1.clone();
orResult.or(bitSet2);
BitSet xorResult = (BitSet) bitSet1.clone();
xorResult.xor(bitSet2);
BitSet notResult = (BitSet) bitSet1.clone();
notResult.flip(0, 8);
System.out.println("bitSet1: " + bitSet1);
System.out.println("bitSet2: " + bitSet2);
System.out.println("AND result: " + andResult);
System.out.println("OR result: " + orResult);
System.out.println("XOR result: " + xorResult);
System.out.println("NOT result: " + notResult);
}
}
In this example, we create two BitSets and set some bits in each of them. We then perform bitwise AND, OR, XOR, and NOT operations on the BitSets using the and(), or(), xor(), and flip() methods, respectively. We print the results of each operation using the toString() method.
In Java, the Bitset class is part of the java.util package and provides an efficient way to manipulate sets of binary values. We can create a Bitset object and perform various operations on it using the following methods:
set(int index): sets the bit at the specified index to true.
clear(int index): sets the bit at the specified index to false.
get(int index): returns the value of the bit at the specified index.
and(Bitset set): performs a bitwise AND operation between this Bitset and the specified Bitset.
or(Bitset set): performs a bitwise OR operation between this Bitset and the specified Bitset.
xor(Bitset set): performs a bitwise XOR operation between this Bitset and the specified Bitset.
Applications in solving problems
Bitsets are useful in a variety of programming problems where we need to efficiently store and manipulate sets of binary values. Here are some examples:
Sieve of Eratosthenes:The Sieve of Eratosthenes is an algorithm used to find all prime numbers up to a given limit. We can implement this algorithm using a bitset, where each bit represents whether a number is prime or not. Initially, all bits are set to 1, except for the first two bits (0 and 1) which are set to 0. We start from the first prime number (2) and set all its multiples to 0. Then, we move to the next prime number (3) and repeat the process until we reach the limit.
Finding missing numbers:We can use bitsets to efficiently find missing numbers in an array. Let's say we have an array of n integers and we know that the array contains all integers from 1 to n, except for one. We can create a bitset of size n and set the ith bit to 1 if i is present in the array. Then, we can iterate over the bitset and find the index of the missing number.
Optimizing memory usage:In some cases, we need to store large sets of boolean values in memory. Using an array of boolean values can be memory-intensive, especially if most of the values are false. Bitsets can help us optimize memory usage in such cases. For example, if we need to store the presence of letters in a string, we can use a bitset of size 26 (one bit for each letter) instead of an array of size 26.
Hope this blog tutorial has been helpful to you. If you have any remaining doubts or suggestions, please feel free to share them in the comments below. We would be glad to receive your feedback.
💛 You can Click Here to connect with us. We will give our best for you.
Comments
Post a Comment