Number system and bitwise operations

In this article, we will discuss

• What is the number system?
• Binary number System.
• Bitwise operators
• Basic Questions

Any number system requires two things

1. Symbols
2. Base (group size)

Humans in daily life use a decimal number system that contains 10 symbols (0-9) and as it has 10 symbols we call it to base 10.

So suppose we want to mention 287 in decimal it can be represented as

287 = 200 + 80 + 7
   =  2 * 10^2 + 8*10 + 7

There are also other number systems available like,

• Binary number system ( 2 symbols(0, 1), base 2)
• Octal number system. (8 symbols(0 - 7), base 8)
• Hexadecimal number system. (16 symbols(0-9, A-F), base 16)

We will mostly cover about binary number system in this article.

Binary Number System

The binary number system uses only two symbols 0 and 1 and is expressed with base 2. Let's look at some examples.

I would recommend watching the below video to learn more about binary number systems.

Bitwise Operators

• bitwise AND (&) operator: In AND operation, if both bits are set then output is 1 otherwise the output is 0. Below is the truth table for the AND operator.

• bitwise OR (|) operator: In OR operation, if any bit is set then output is 1. If only both bit is 0 then output is 0. Below is the truth table for the OR operator.

• bitwise XOR (^) operator: If both bits are the same then output is 0 otherwise output is 1.

• bitwise NOT (!) operator: It reverses the bit. so if the input is 0 it returns 1 and vice versa.

• The << (left shift): It takes two numbers, left shifts the bits of the first operand, the second operand decides the number of places to shift. Example: a << 1 --> Left shift number a by 1 bit. 5 << 1 = 10 5 << 2 = 20

In a left shift if we shift by one bit then the number will be multiplied by 2. so if we left shift by two bits then it will be multiplied by 2*2 = 4 and so on.

• The >> (right shift): It takes two numbers, right shifts the bits of the first operand, the second operand decides the number of places to shift.

10 >> 1 = 5 20 >> 2 = 5

In a right shift if we shift by one bit then the number will be divided by 2. so if we right shift by two bits then it will be divided 4 and so on.

Basic Questions

I am posting some questions below try it yourself. Post your answer in the comment section and I will add my answer later.

Q - 1:

Given an array of integers A, 
every element appears twice except for one. Find that single one.

NOTE: Your algorithm should have a linear runtime complexity. 
Could you implement it without using extra memory?

Example Input
Input 1:
 A = [1, 2, 2, 3, 1]
Input 2:
 A = [1, 2, 2]


Example Output
Output 1:
 3
Output 2:
 1

Q - 2:

Number of 1 Bit
Problem Description

Write a function that takes an integer and returns 
the number of 1 bits it has.

Problem Constraints
1 <= A <= 109

Example Input
Input1:
11

Example Output
Output1:
3