23. Bit manipulation

  • swap 2 numbers✅
  • get i-th bit (check set or not)✅
  • toggle i-th bit ✅
  • set or clear i-th bit✅
  • check number odd or not✅
  • remove last set bit⭐✅
  • count set bits⭐✅
  • set rightmost unset bit✅
  • check if power of 2✅
  • divide 2 numbers⭐✅
  • min flips in bits to convert A to B
  • power set
  • xor of all numbers from L to R✅
  • all no.s appear thrice except 1 number
  • all no.s appear twice except 2 numbers

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

NOTE :-

1. decimal to binary  &  binary to decimal  conversion

2. since int is of  4byte i.e.,32 bits, so if int x=17 (no. is just of 5 bits here) so rest 27 bits stores 0

3. One's complement- convert to binary and then 1 ki jagah 0 and vice versa

    Two's complement- add 1 to the one's complement.

4. (-ve) no.s in binary form-

  • for decimals- an extra bit is appended at the start of binary no. to store info for sign , where 0 us for (+) and 1 for (-) numbers
  • for integers- neg no.s are stored as 2s complement in binary form...

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

5. XOR(^): ⭐

same bits ka xor gives 0, different ka gives 1

a^a = 0,     a^0 = a

odd no. of 1s hain => ans is 1, else ans is 0

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

6. NOT(~):⭐

~x is the 1s complement of x

  • take 1s complement of x
  • if 1st bit is 1 then ~x is a negative number, so take 2s complement of ~x, 
  • else ~x obtd by just the 1st complement of x is the answer

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

7. Shift operators:

right shift:- moves all bits to the right, discards the rightmost bits, and fills the empty leftmost bits based on sign.

n>>k     =     n / (2^k)

-----

left shift :- moves all bits to the left and fills the empty rightmost bits with 0s.

n<<k      =    n* (2^k)

e.g., 1<<2 in binary gives 100

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

8. overflow if INT_MAX << 1

9. INT_MAX is (2^31) - 1

    INT_MIN is (-2^31)

10. Bits are counted from right(LSB) to left(MSB) in a binary no.

11. no. of bits in a number are logN(base 2)

12. bit positions start from 0th bit being considered at LSB

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

Converting decimal to binary and store in normal order (like for 16 --> 10000)

1. using strings (displays in MSB to LSB, need to reverse the string)

2. using vectors (displays in MSB to LSB, need to reverse the vector)

3. using bitset (although it displays from MSB to LSB, yet it gives LSB at b[0] )
fix size array of bits- max: 1e7

b.count() counts set bits

b.flip(i) flips i-th bit

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

1. Swap 2 no.s w/o temp-

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

2. Check if i-th bit is set-

Brute- ( time: logN,  space: logN )            using binary string

convert number to a binary string--> reverse the string --> check i-th bit in it 

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

Better-  ( time: O(1),   space: O(N)  )        use bitset

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

Optimal- ( time: O(1),   space: O(1) )        use bitwise operations-

 if i-th bit is set, then if 1<<i ke saath & lunga toh bas usi posn pe 1 bachega and ans!=0 aayega

Method-1.)  take & of original number with 1 being shifted left

  


Method-2 .)    take & of number (being right shifted) with 1
--------------------------------------------------------------------------------------------------------
3. Set or clear i-th bit-

we are assuming 0 based indexing from LSB

set i-th bit:- jis bit pe 1 set krna sirf uska OR lelo 1 ke saath

clear i-th bit:- jis bit pe 0 set krna sirf uska & lelo 0 ke saath


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

4. Toggle i-th bit-

take xor with 1 at the i-th position in binary form, as XOR flips a bit


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

NOTE-

1. (n-1) mein rightmost set bit 0 ho jata hai and uske right wale sab 1 ban jaate hain
2. (n+1) mein rightmost unset bit 1 ban jata hai and uske right wale sab 0 ban jate hain.

3. Even number ki binary form me sirf ek 1 hoga and odd mein bahut saare 1s and 0s
4. LSB of an odd number is always 1 
5. if (x  & 00000001 == 1 ) then x is odd

6. (n/2) can be written as (n>>1)

7. XOR helps where we want to check ki is position pe bit alag hai ki nhi as same walo pe 0 deta hai output...

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

5. Remove last set bit-

it means LSB se MSB tak chalte chalte jo pehli set bit aayegi usko clear krna hai

ANS:   n & (n-1) 

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

6. Check if no. is power of 2 or not-

binary form me sirf ek set bit hoga
ans:  n & (n-1) agar 0 aara then yes else no
-------------------------------------------------------------------------------------------------------------
7. Count set bits-
Method-1:
2 se divide krke remainder check krte raho and counter badhate raho and n ko n/2 krte raho
------------------------
Method-2:
__builtin_popcount(n) // n is int
__builtin_popcountl(n) // n is long
__builtin_popcountll(n)  // n is long long
-------------------------
Method-3:
n & (n-1) krte krte LSB se MSB tak saari set bits clear krte raho aur counter badhate raho
---------------------------------------------------------------------------------------------------------------
Set the rightmost unset bit

n =  n | (n+1),   since n+1 has the rightmost unset bit as 1 ans usse leke LSB tak waale sab as 0 and usse leke MSB tak ke same
---------------------------------------------------------------------------------------------------------------

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

if we take XOR of given number and goal then, in the answer we will get 1 at all those places jinko mujhe change krna tha given number ko goal banane k liye...
answer will be number of set bits in the xor of given number and goal...
--------------------------------------------------------------------------------------------------------
2. Power Set-

same time complexity as of recursion but less space as compared to recursion.

------------------------------------------------------------------------------------------------------------
3. Divide 2 numbers without (/) operator :
  • truncate the decimal part to 0 and then return the quotient
  • if quotient > INT_MAX return INT_MAX
  • if quotient < INT_MIN return INT_MIN
Brute-  REPEATED SUBTRACTION
divisor ko tab tak add krdo khudme hi jabtak vo dividend se chota ya equal hai
-------------------------------------------------
Better-         SHIFT SUBTRACTION

time- (logN)^2

dividend me se har baar divisor*(smtg) ghatate rho, jab tak (dividend < divisor) na ho jaaye...here smtg is 2^.. such that divisor*this thing, is max thing which can be subtracted from current dividend
e.g., for 22 , max no which can be subtracted is 3*(2^2) = 12,
        for 10,    it is 3*(2^1)=6
        for 4, it is 3*(2^0)=3
        since 1<3 so stop
and quotient is 4+2+1

------------------------
d<<x means d*(2^x)
---------------------------------------------------------------------------------------------------------------
4. XOR of all numbers from L to R :-

(L se R tak ka XOR)     =     (1 se L-1 tak ka XOR) ^ ( 1 se R tak ka XOR )





----------------------------------------------------------------------------------------------------------------------------
5. Every number appearing thrice except one number-

BETTER 1-
answer me vo wale bit posn pe 1 hoga jinpe number of 1s not a multiple of 3 hoga

BETTER 2-  
Sort krke same wale ikhate ho jayenge toh 3 me se bich wale elmt pe check kro ki vo apne pichle wale ke equal hai kya hai toh +3 krke aage badho index pe...

OPTIMAL- (BUCKETS CONCEPT)

                        
-------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------
6. All numbers appear twice except 2 numbers-

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

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more