### 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

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