Introduction to Bit Manipulation

Bit manipulation is the act of algorithmically manipulating bits or binary digits.

Convert Decimal to Binary

Explanation

Divide the number by 2

Keep track of the remainder

Repeat the process until the number is 0 or 1

Reverse the remainders

Example:

Decimal Number: 5 # Convert this number to binary
Binary Number: 101 # 5 in binary

Convert Binary to Decimal

Explanation

Multiply each bit by 2 raised to the power of its position

Add the results

Example:

 
Binary Number: 101 # Convert this number to decimal
Decimal Number: 5 # 101 in decimal
 
# Calculation
1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 5

1's Complement

Explanation

Convert the Decimal Number to Binary Number

Now just flip the bits

Example:

Decimal Number: 5 # Convert this number to 1's complement
Binary Number: 101 # 5 in binary
1's Complement: 010 # Flipped the bits

2's Complement

Explanation

Convert the Decimal Number to Binary Number

Now flip the bits

Add 1 to the flipped bits

Example:

Decimal Number: 5 # Convert this number to 2's complement
Binary Number: 101 # 5 in binary
1's Complement: 010 # Flipped the bits
2's Complement: 011 # Added 1 to the flipped bits

Bitwise AND Operator (&)

Explanation

This is the truth table for the bitwise AND operator

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

Example:

A = 5 # 101
B = 3 # 011
 
A & B = 1 # 001
 
# Calculation
101
011
---
001

💡

Trick to remember: 1 & 1 = 1, else 0

Bitwise OR Operator (|)

Explanation

This is the truth table for the bitwise OR operator

A	B	A \| B
0	0	0
0	1	1
1	0	1
1	1	1

Example:

A = 5 # 101
B = 3 # 011
 
A | B = 7 # 111
 
# Calculation
101
011
---
111

💡

Trick to remember: 0 | 0 = 0, else 1

Bitwise XOR Operator (^)

Explanation

This is the truth table for the bitwise XOR operator

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

Example:

 
A = 5 # 101
B = 3 # 011
 
A ^ B = 6 # 110
 
# Calculation
101
011
---
110
 
This is the binary representation of 6

💡

Trick to remember: 1 ^ 1 = 0, 0 ^ 0 = 0, else 1

Bitwise NOT Operator (~)

Explanation

This is the truth table for the bitwise NOT operator

A	~A
0	1
1	0

Example:

A = 5 # 101
~A = -6 # 010
 
# Calculation
101
---
010
 
This is the binary representation of -6
 
How? 2's complement of 6 is 010

💡

Trick to remember: 1 becomes 0, 0 becomes 1

Left Shift Operator (<<)

Explanation

Left shift operator shifts the bits to the left by n positions

Example:

A = 5 # 101
 
A << 1 = 10 # 1010

Right Shift Operator (>>)

Explanation

Right shift operator shifts the bits to the right by n positions

Example:

 
A = 5 # 101
 
A >> 1 = 2 # 10

README 1. Swap two numbers