23. Bit manipulation

Note:-

1. decimal to binary  &  binary to decimal conversion
----------------
2. int type variable stores data upto 32 bits, so if value is of x bits only then remaining 32-x bits are 0
-----------------
3. One's complement- flip all bits of the number in binary form
    Two's complement- add 1 to the one's complement.
------------------

4. (-ve) integers:    stored as 2s complement ⭐

    (-ve) decimals:   an extra bit is appended at MSB of binary form of number where,
                               0 for (+) and 1 for (-)⭐
-------------------------
5. XOR: ⭐
1^1=0,      1^0=1
a^a = 0,     a^0 = a
-------------------------
6. NOT:⭐
~x = 1s complement of x

in decimal form: (~x = -x-1)

converting ~x from binary to decimal:-

- if (MSB=1) then, ~x is a negative number => take 2s complement of ~x & add negative sign in the decimal version of the 2s complement of ~x to get answer⭐
- if (MSB=0), then this is the required answer, just convert to decimal form
--------------------------
7.1 Right shift :- 
fills empty leftmost bit based on sign⭐
n>>k     =     n / (2^k)
--------------------------
7.2 Left shift :-
fill the empty rightmost bit with 0⭐
n<<k      =    n* (2^k)
--------------------------
8. (INT_MAX << 1) => overflow

9. Bits positions are counted from LSB to MSB
10. no. of bits in a number = logN(base 2)⭐
------------------------------------------------------------------------------------------------------------

Decimal to Binary conversion

(display binary form from MSB to LSB)

1. using strings

----------------------------------------------------
2. using vectors

---------------------------------------------------------------------------------------------------------------
Note- BITSET (ignore for interviews)

1.  bitset<x>b(n) displays binary form of n in x-bit
2.  b[0] gives LSB
3.  cout<< b , prints binary form of n, from MSB to LSB

4. Useful functions:
    b.count() => count set bits
    b.flip(i) =>   flips i-th bit
    b.test(i) => if true then i-th bit is set
5.  fix size array of bits- max: 1e7
------------------------------------------------------------------------------------------------------------

1. Swap 2 numbers⭐
(w/o temp)

-------------------------------------------------------------------------------------------------------------

2. Check if i-th bit is set-

Brute- time: logN,  space: logN             

convert given decimal number to binary form & then check if i-th bit is set or not 
-------------------------

Better-  time: O(1)   space: O(N)          
using bitset

b[i] will return value at i-th bit position
------------------------
Optimal-  time: O(1)    space: O(1)   
using bit manipulation

---------------------------------------------------------------------------------------------------------------

3. Set or clear i-th bit-⭐

set i-th bit:- take OR with 1 at that bit position 

clear i-th bit:- take AND with 1 at that bit position

---------------------------------------------------------------------------------------------------------------

4. Toggle i-th bit-⭐

take xor with 1 at the i-th position 
as XOR with 1 toggles the bit

------------------------------------------------------------------------------------------------------------

Note-

1. (n-1) => rightmost      set bit becomes 0 & all bits to its right becomes 1 

2. (n+1) => rightmost unset bit becomes 1 & all bits to its right becomes 0 

3. Even number: only 1 set bit⭐
4. Odd number:  LSB = 1, always

5. How to find if bit at position "i" is same or different, in two given numbers => XOR⭐

6. we assume 0 based indexing from LSB

--------------------------------------------------------------------------------------------------------------

5. Clear rightmost set bit⭐

take AND of (n) with (n-1) 

--------------------------------------------------------------------------------------------------------------

6. Check if no. is power of 2 or not-
(check if number is even or not)

since even number will have only 1 set bit⭐
hence if we clear that bit, then number reduces to 0

-------------------------------------------------------------------------------------------------------------

7. Count set bits-

Brute:

modifying the decimal to binary conversion logic to count set bits

------------------------

Better:

using popcount function which directly returns number of set bits in a number

-------------------------

Optimal:

using rightmost set bit concept

repeatedly remove rightmost set bit and keep a track of number of set bits using a counter

---------------------------------------------------------------------------------------------------------------

8. Set the rightmost unset bit

n =  n | (n+1)
---------------------------------------------------------------------------------------------------------------

1. Minimum flips in bits to convert a number A into B-

A^B gives 1 at places where bit differs in A and B

hence, 
answer = number of set bits in A^B

--------------------------------------------------------------------------------------------------------------

2. Find Power Set of a given array-
(using Bit Masking)⭐
(n <= 32)

Power set = all subsets = all subsequences
---------------------------------
since,  no. of subsets = 2^n
Hence, we can associate each subset with a number from 0 to (2^n)-1, each number representing a bit mask of size n
e.g., in {a,b,c} total subsets are 2^3 = 8, hence we create 8 bit masks each of size 3,
where for example- {a,c} is represented as 101

-------------------------------
1. 0 se (2^n)-1 tak saare numbers lelo
2. har number mein jaha jaha set bit hai, vo wale corresponding elements lelo array se for current subset

3. is ek subset ko power set mein daalo and repeat. 

------------------------------------------------------------------------------------------------------------

3. Divide 2 numbers without (/) operator :

- truncate the decimal part to 0 and then return the quotient
- Clamp result if it exceeds 32 bit signed integers limits

------------------------------------------------
Brute- time: O(n),  where n= dividend

Division is REPEATED SUBTRACTION of divisor from dividend

or, we can repeatedly add divisor till it exceeds dividend

-------------------------------------------------

Optimal-  time ~ O((logN)^2)    

using SHIFT SUBTRACTION⭐

1. To speed up division, we subtract (divisor * powers of 2) 
    At any iteration this qty is max stuff which can be subtracted from current dividend

2. Do this till (dividend > divisor)

3. final quotient is sum of these extra Coefficients with divisor

---------------------------------------------------------------------------------------------------------------
Note-⭐

XOR in [1,n] follows a pattern based on n%4

---------------------------------------------------------------------------------------------------------------

4. XOR of all numbers in [L,R]:-⭐

Optimal: time: O(1)

xor in [L,R] = (xor in [1,L-1] ) ^ (xor in [1,R])

----------------------------------------------------------------------------------------------------------------------------

5. Every number appearing thrice except one number-

Brute-  time: O(nlogn)

1. Sort the array
2. In every triplet see if the middle elmt is same as prvs element
3. When not equal, then that prvs element is ans.

-------------------------------------------------------

Optimal:   time ~ O(n)⭐

1. for every bit position, traverse the array & count how many numbers have this bit set
2. this bit will be 1 for the answer only if, the count is not a multiple of 3

-------------------------------------------------------

Extra- (FSM trick)- ignore

                         

-------------------------------------------------------------------------------------------------------------------------

NOTE-
Extracting rightmost set bit-
take xor of (original number) with (this number having rightmost set bit cleared)

-------------------------------------------------------------------------------------------------------------------------

6. All numbers appear twice except 2 numbers-⭐

1. XOR the entire array and thus we get, A^B 
2. (A^B!=0) => there is atleast one bit where both A & B differ (or, there is atleast one set bit in A^B)

3. Pick rightmost set bit in A^B
4. Split array into 2 groups- one having this bit=1, other having this bit=0
5. A and B go to different groups
6. Now xor inside each of the groups, thus we get A and B
----------
Concepts used :
- clear rightmost set bit
- extract rightmost set bit
- if i-th bit is set or not
---------

------------------------------------------------------------------------------------------------------------------------