Bit Manipulation-DSA

Question 1

how to find binary equivalent of any decimal number

Answer 1

1. divide it by 2

Question 2

how to convert binary to decimal

Answer 2

1. 1101 to decimal
2. start from right, move towards left

3.
(that number * 2) raise to the power of that index + (that number * 2) raise to the power of that index + (that number * 2) raise to the power of that index

add all numbers

O/p is in decimal…

Question 3

write a function that will take decimal and return its binary

Answer 3

string count2Binary(int n){
res = “”

while(n != 1){
if (n % 2 == 1) res += “1”

else res += “0”;

n = n/2;

}

reverse(res);

return res;
}

Question 4

write a function that takes binary and return its decimal equivalent

Answer 4

int convertToDecimal(string x){
int len = x.length();
for(i =len - 1; i–){
if(n[i] == ‘1’)
num = num + p2;
p2 = p2 * 2;
}

return num;
}

===
TC => O(len)
SC => O(1)

Question 5

what happens when we write
int x = 13

Answer 5

13 gets converted to binary, but 13 requires only 4 bits

Question 6

13 requires only 13 bits, what happens with other remaining bits

Answer 6

remaining bits will be stored with zero’s

Question 7

how many bits required to store int

Answer 7

32 bits

Question 8

if x is stored as binary, when we print int, how does we get int, like 13 in this example

Answer 8

reverse conversion of binary / bits happens, 13 gets converted to binary

Question 9

int is 32 bits, how many bits for long long

Answer 9

64 bits

===

most of the problems of long long can be solved if you know int concept

Question 10

what is ones complement.
Que. what is ones complement of 13

Answer 10

13 => (1101)2 base 2
flip all the bits
=> 0010

Question 11

what is twos complement

Answer 11

step 1: figure out ones complement of number
step 2: add one to it

Que. what is 13’s two complement

1. 13 => (1101)base 2
2. ones complement => 0010
3. add one => 0011

Question 12

AND operator explain

Answer 12

all true => true
one false => false

x = 13 & 7
= 5

1 1 0 1 => 13
0 1 1 1 => 7
———-
0 1 0 1 => 5

Question 13

OR operator

Answer 13

one true => true
all false => false

x = 13 | 7

1 1 0 1
0 1 1 1
———-
1 1 1 1 => 15

Question 14

XOR

Answer 14

number of 1s => odd -> one
number of 1s => even -> zero

Question 15

right shift operator

Answer 15

x = 13&raquo_space; 1

1101

last one goes off the clip
0000000…110

=> o/p will be 6

x = 13&raquo_space; 2
last two numbers, will go off the clip
000000…11

o/p => 3

x = 13&raquo_space; 4

00000000….1101
0000000000000

all of them go off the clip

Question 16

formula for right shift

Answer 16

x&raquo_space; k = ( x / 2 power k )

x divide by 2 and twos power will be K

Question 17

how does computer stores minus and positive numbers, particular positive / negative thing

Answer 17

int are stored in 32 bits, and the first bit or the last bit if you count from end, 31st bit is reserved for sign

and rest of bits are used to store numbers

Question 18

What bit for positive

Answer 18

zero is used for positive sign

Question 19

what bit is used for negative

Answer 19

one is used for negative

Question 20

x = 13, how this will be stored

Answer 20

0 0 ……. 1101
|
|

for sign, positive

Question 21

x = -13, how this will be stored, how does the computer stores it

Answer 21

using two’s complement

first thing we do is we write down positive 13 bits

which is basically starting from 0.

0 0 0 0 ……. 1 1 0 1

now whenever computer has to store number into its negative form, computer converts it into it’s two’s complement

• to convert bits to its twos complement first we perform ones complement [flip the bits]
• in second step we add one to it

0000……1101
1111…….0010 => ones complement
0000…………..0 => add one
——————————————————-
11111……0011
|
|
|
the last bit represents negative sign

Question 22

what is largest integer that int data type can save

Answer 22

last is reserved for sign, 31 bits are remaining

2 power 31 - 1

this is the largest value we can store in int variable

Question 23

what is INT_MAX you seen in code

Answer 23

INT_MAX is that largest value

Question 24

what is smallest number that int variable data type can save

Answer 24

-2 power 31

INT_MIN

=> 1 0 0 0 0 …….. 0

Question 25

what is left shift operator, how to represent left shift operator

Answer 25

«

Question 26

13 &laquo_space;1

Answer 26

=13 &laquo_space;1
=> 26

the last bit, or 31st bit goes off the clip

0 0 0 ………… 1 1 0 1
0 0 0 …………1 1 0 1 0

• the remaining space of first index bit is filled with zero bit, not matter what first bit was
• first i use to think that if zero is removed, then it gets added to first index position

Question 27

how does it work mathematically

Answer 27

num &laquo_space;k
= num * 2 power k

13 &laquo_space;1
= 13 * 2 power 1

Question 28

when does overflow causes

Answer 28

34:01

Question 29

NOT ~ operator