Bit masking is a process of using binary digits (bits) to store and manipulate data. It involves using bitwise operators and
Some common bitwise operators are as follows:
AND (&
): In bit masking, the AND operator resets the selective bits. We use the AND operator with a mask of zeros at selective bits to set bits to zero.
OR (|
): Similarly, the OR operator enables the selective bits. We use the OR operator with a mask of ones at selective bits to set bits to the value of one.
XOR (^
): The XOR operator is used to toggle bits. We use the XOR operator with a mask of ones at selective bits to flip the bit values.
NOT (~
): The NOT operator is used to inverse the bits. We use the NOT operator to take the complement of the values. It doesn’t require any mask value to operate and changes the complete input.
SHIFT LEFT (<<
): The SHIFT LEFT operator moves the bits of a binary number to the left by a specific number of positions. We use this operator to perform the multiply operation on the number by 2 raised to the power of the shift number, e.g., a << b
is equivalent to a * 2^b
.
SHIFT RIGHT (>>
): Conversely, the SHIFT RIGHT operator moves the bits of a binary number to the right by a specific number of positions. We use this operator to perform the division operation on the number by 2 raised to the power of the shift number, e.g., a >> b
is equivalent to a / 2^b
.
The bits on the left side will be truncated using the SHIFT LEFT operation. Similarly, the bits on the right side will be truncated using the SHIFT RIGHT operator.
Let’s perform the bitwise operations in the following playground:
element = 46 # 00101110mask = 170 # 10101010shift = 3 # 00000011elementbin = format(element, '08b')maskbin = format(mask, '08b')shiftbin = format(shift, '04b')# AND operation (00101110 & 10101010 = 00101010)print(f'{elementbin} & {maskbin} = ', format(element & mask, '08b')) # 00101010# The format() function with '08b' argument is used to print in 8-bit binary format# OR operation (00101110 | 10101010 = 10101110)print(f'{elementbin} | {maskbin} = ', format(element | mask, '08b')) # 10101110# XOR operation (00101110 ^ 10101010 = 10000100)print(f'{elementbin} ^ {maskbin} = ', format(element ^ mask, '08b')) # 10000100# NOT operation (~00101110 = 11010001)print(f'~{elementbin} = ', format(~element, '08b')) # -0101111# NOT operation (~11010001 = 00101110)print(f'~({format(~element, "08b")}) = ', format(~(~element), '08b')) # 00101110# SHIFT LEFT operation (00101110 << 00000011 = 101110000)print(f'{elementbin} << {shiftbin} = ', format(element << shift, '08b')) # 101110000# SHIFT RIGHT operation (00101110 >> 00000011 = 00000101)print(f'{elementbin} >> {shiftbin} = ', format(element >> shift, '08b')) # 00000101
In the code above:
Lines 1–3: We define element
, mask
, and shift
variables to demonstrate the working of different bitwise operations.
Lines 5–7: We store the binary of these three variables to display in the output. The format()
function is used to get the binary value of the variable. The '08b'
argument of the format()
function fixed the minimum 8-bit binary output.
Line 10: We perform the bitwise AND operation using the &
operator between element
and mask
and display the output.
Line 14: We perform the bitwise OR operation using the |
operator between element
and mask
and display the output.
Line 17: We perform the bitwise XOR operation using the ^
operator between element
and mask
and display the output.
Lines 20–22: We display the output of the bitwise NOT operation on element
and the ~element
using the ~
operator.
Line 25: We perform the SHIFT LEFT operation by three bits using the <<
operator on element
and display the output.
Line 28: We perform the SHIFT RIGHT operation by three bits using the >>
operator on element
and display the output.
A mask decides which bits to keep, reset, toggle, or update from a binary number to manipulate the information. Bit masking is used to mask a specific value using a bitwise operation to achieve this. It can solve a wide range of problems. Let’s discuss some examples of it.
Instead of using multiply or divide operators, we can use shift operators to double or half a value. We can use the SHIFT LEFT operator to double and the SHIFT RIGHT operator to half the value.
element = 46print("Element:", element) # 46print("Doubling the element:", element<<1) # 92print("Halving the element:", element>>1) # 23
Instead of using a loop to calculate the power of 2 raised to some power of k
(
k = 10print("2 raise to the power of", k, "is:", 1<<k) # 1024print("2 raise to the power of", k, "in binary is:", format(1<<k, '08b')) # 10000000000
In the playground above, we’ve seen that we can append zeros to a number by using the SHIFT LEFT operator. Let’s create a mask using the SHIFT LEFT operator. Now, we can use the AND operator to check the value of the
element = 46 # 00101110i = 4mask = 1<<i # 10000if(element & mask):print(f"The value of {i}-th bit of {element} is 1")else:print(f"The value of {i}-th bit of {element} is 0")
Similarly, we can toggle the
element = 46 # 00101110i = 4mask = 1<<i # 10000print("Element:", element) # 46print(f"Toggling the {i}-th bit of {element}:", element ^ mask) # 62
In computer science, bit masking is used in various applications. Some of them are as follows:
Flag management: Flags are important to perform any operation, especially in low-memory systems. Using the entire bit for one flag would be critical in such scenarios. Instead, we can utilize each bit in a bit mask that can represent a different flag and use bitwise operations to check or modify the state of these flags.
Network programming: In the field of networking, bit masking can be utilized to extract and manipulate the information from IP addresses and port numbers.
Mathematical operations: The shift operators are used to perform rapid multiplications and divisions by the powers of 2. This is useful in low-level programming or embedded systems.
Optimizations: Bit masking is used in different fields to apply the optimizations, e.g., in graphic processing and gaming, bit masking is often used to represent image masks and collision detection. Similarly, in set-based data structures, we can utilize the bit masks to represent a set of elements to optimize set operations.
Permissions and access control: In security systems, each bit can represent a specific permission or access control. Bit masking plays an important role in extracting the permissions and access and modifying the access rights of a user.
Bit masking has its own benefits and limitations. Here are some pros of using bit masking:
Memory efficiency: Bit masking leads to memory saving by representing multiple boolean flags as a single integer value.
Increased speed: Bit masking operations are bit-level, and they usually exhibit faster execution compared to conventional operations such as addition or multiplication.
Cleaner code: Bit masking leads to cleaner and more readable code, especially when dealing with problems involving sets, subsets, or combinations.
Logical operations: Bit masking utilizes bitwise operations, and bit shifts are computationally efficient, which makes them suitable for certain types of logical operations in algorithms. For example, in a multiplexer with 8 channels of data lines, we can use bit masking in two ways. To receive data from a specific channel, we can either utilize the OR and NOT operations to change a three-bit code to select the channel, or we can use SHIFT LEFT and SHIFT RIGHT operations in an 8-bit code to select the channel.
Let’s discuss some cons of using bit masking:
Complexity for beginners: Bit masking can be challenging for beginners to understand, as it involves working with binary representations and bitwise operations.
Limited range: The number of bits in the bit mask puts a limit on the size of the sets or combinations that can be efficiently represented. Larger sets require more bits, leading to increased complexity.
Not suitable for all problems: Bit masking is powerful in certain scenarios, but it may not be the optimal solution for all types of problems. Depending on the problem characteristics, other techniques or data structures might be more appropriate.
Exponential time complexity: The time complexity can be exponential in some bit masking applications, especially those involving subsets or combinations. This makes bit masking less suitable for large datasets.
Suppose you are working on designing an audio mixer control panel for a new digital audio workstation. Your task is to implement a system that allows users to control the input channels for left, right, up, and down audio signals. To achieve this, implement the following to manage the activation and deactivation of each channel:
Create a 4-bit flag to indicate the input from left, right, up, and down channels.
Create masks to active and inactive each flag separately.
Turn left and up channels active initially using the bitwise OR operator, and display the flags.
Now, toggle the right and up channels using the bitwise XOR operator and display the flags.
Implement the challenge in the following playground:
# Implement your solution here