Bitwise Manipulation: Introduction

Let’s go over the bitwise manipulation pattern, its real-world applications, and some problems we can solve with it.

We'll cover the following

Overview#

Bitwise Manipulation is the process of modifying bits algorithmically using bitwise operations. Logical bitwise operations are the fastest computations, because processors natively support them. This approach generally leads to efficient solutions in problems where we can efficiently transform the input into its binary form or manipulate it directly at the bit level to produce the required output.

A bitwise operation works on a bit string, bit array, or a binary numeral. Bitwise operators take bits as their operands and calculate the corresponding bit value in the result.

The table below describes the functioning of the four widely used bitwise operators:

Operator

Functioning

NOT(~)

This is a unary operator. If the argument is a 1-bit, flip it to change a 1 to a 0, and vice versa. If the argument is a string of bits, all bits in the string are reversed, turning 1's into 0's and vice versa.

AND(&)

If both the bits are 1, then 1 is returned. Otherwise, 0 is returned.

OR(|)

If either of the bits is 1, then 1 is returned. Otherwise, 0 is returned.

XOR(^)

If both bits are equal, then 0 is returned. Otherwise, 1 is returned.


The following illustration demonstrates how the XOR operator works.

Created with Fabric.js 3.6.6 Result 0 Number 1 1 0 1 0 0 1 Number 2 1 1 0 1 1 1 Both the bits are same, hence taking XOR of both thebits will return 0.

1 of 6

Created with Fabric.js 3.6.6 Number 1 1 0 1 0 0 1 Number 2 1 1 0 1 1 1 Result 0 1 The rest of the problem will be solved by the same approach. Now both the bits are different, hence taking XOR of both the bits will return 1.

2 of 6

Created with Fabric.js 3.6.6 Number 1 1 0 1 0 0 1 Number 2 1 1 0 1 1 1 Result 0 1 1

3 of 6

Created with Fabric.js 3.6.6 Result 0 1 1 1 Number 1 1 0 1 0 0 1 Number 2 1 1 0 1 1 1

4 of 6

Created with Fabric.js 3.6.6 Result 0 1 1 1 1 Number 2 1 1 0 1 1 1 Number 1 1 0 1 0 0 1

5 of 6

Created with Fabric.js 3.6.6 Number 1 1 0 1 0 0 1 Number 2 1 1 0 1 1 1 Result 0 1 1 1 1 0

6 of 6

Examples#

The following examples illustrate some problems that can be solved with this approach:

Created with Fabric.js 3.6.6 x 5 x 10 Swap two numbers without using a temporary variable Take XOR of x and y and storing the result in x: Take XOR of x and y and now storing the result in y: Lastly, take XOR of x and y again and now store the result in x: x 1 0 1 0 y 0 1 0 1 x 1 1 1 1 y 1 0 1 0 x 0 1 0 1 y 5 y 10 Note that if we now convert both the values back into the decimal numbersboth the variables have their values swapped. Convert input numbers to their binary form:

1 of 2

Created with Fabric.js 3.6.6 Input strings: If the characters of both string are same, concatenate "0"to the result variable. Else "1" is concatenated. str1 "0010" str2 "0011" result "0001" Blue color representsthat two charactersare the same, and purplerepresents that twocharacters are different. Compare the character of both strings one by one Compare both strings character by character. str1 0 0 1 0 str2 0 0 1 1

2 of 2

Does my problem match this pattern?#

  • Yes, if either of these conditions is fulfilled:
    • The input data can be usefully manipulated at the level of the primitive bitwise logical operations, in order to compute some portion or all of the solution.
    • The input data is unsorted, and the answer seems to require sorting, but we want to do better than O(nlog⁡n)O(n \log n).
  • No, if the input data type is not in numeric form or cannot be converted to numeric form.

Real-world problems#

Many problems in the real world share the bitwise manipulation pattern. Let’s look at some examples.

  • Bit fields (flags): They can be used to implement a way of representing things whose state is defined by a boolean expression.

  • Cryptography: They can be used to encrypt and decrypt any sensitive data.

  • Releasing Process Lock: Given a list of integers, they can be used to represent the order in which the lock was acquired and released in an operating system.

Strategy time!#

Match the problems that can be solved using the bitwise manipulation pattern.

Note: Select a problem in the left-hand column by clicking it, and then click one of the two options in the right-hand column.

Match The Answer
Select an option from the left-hand side

Swap all the odd and even bits of a given number.

Explanation

Bitwise Manipulation

Check if two integers have opposite signs.

Explanation

Some other pattern

Detect a cycle in an undirected graph.

Explanation

Swap two integers without using an extra variable.

Explanation

Find the Difference