Bit Manipulation - The Coding Shala

Home >> Algorithms >> Bit Manipulation

 In this post, we will learn the basics of Bit Manipulation.

Bit Manipulation

As we know Bit stands for binary digits, the smallest unit of data in the computer. The bit can be either 0 or 1.

What is Bit Manipulation?
Bit manipulation is the process of using bitwise operations on the sequence of bits to get a required result.

First, we will see bitwise operators that we use.

& ( and operator)

If both the bits are 1 then the answer will be 1.
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

let's take an example
A = 5
B = 3
A & B = 5 & 3 = 101 & 011 = 001 = 1

| (or operator) 

Return 1 if any bit is 1.
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

^ (xor operator)

Return 1 if both the bits are different else 0.
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 1

~ (not operator)

Use to flip the bits.
~0 = 1
~1 = 0

>> ( right shift)

Shifts all the bits to right position. (divies by two).

For example:
A = 29 ( 11101)
A >> 2 = 1 1 1 0 1 >> 2 = 0 0 1 1 1 = 7

Note: In the right shift most significant bit(left-most bit) will be replaced by 0.

<< (left shift)

Shifts the bits to the left position. (multiplies by two).

For Example:
A = 29 ( 11101), or ( 0011101)
 A << 2 =  0 0 1 1 1 0 1 << 2 = 1 1 1 0 1 0 0 = 116

Note: In the left shift, the least bit(rightmost bit) will be replaced by 0.

Remember: Logical Operators will return different results than bitwise operations.


What is the difference between Logical Shift(>>) and Arithmetic Shift(>>>)?
The logical shift right inserts a 0 in the sing bit while the Arithmetic shift keeps the sign bit.

Example:
1 0 1 1 0 1 0 1 (-75) >>  1 = 0 1 0 1 1 0 1 0 (90)
1 0 1 1 0 1 0 1 (-75) >>> 1 = 1 1 0 1 1 0 1 0 (-38)

1's Complement

1's complement of a binary number is obtained by inverting(toggling) all the bits in it.

Example:
1's complement of 0101 is 1010.

2's Complement

If we add 1 to the 1's complement of the binary number then we get two's complement of a binary number.

For example:
A = 0111
step 1: intver all bits(one's complement)
A = 1000

step 2: add 1
A = 1000 + 1 = 1001

Why Two's Complement used?
Negative numbers are usually stored in computers in the form of two's complement. For the positive number, we use 0 in the sign bit(leftmost) with its binary number while a negative number is represented as the two's complement with 1 in the sign bit.

Example:
7 = 0 111
-7 = 1 001


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala