1. Swap two numbers - 00:00 2. Check if ith bit is set or not - 3:47 3. set ith Bit - 10:47 4. clear ith Bit - 14:27 5. Toggle ith Bit - 17:52 6.Remove the last set Bit - 21:23 7. Check if a number is power of 2 or not - 28:26 8.count the number of set bits - 31:24
33:00 here you can simply do this public static int countSetBit(int num){ int count = 0; int one = 1; while(num > 0){ if((num & one) == 1){ count++; } num = num >> 1; } return count; }
Yes , but it will work same as toggling if the bit is not set and we don't want that , if the bit will be 0 then also it will be changed to 1 if we do this.
amazing video covering all concepts, soon will be mastering bit manipulations by completing your playlist.Before i used to be scared of seeing bits but now it's easy , even i started to use , today i used in one question and solved that question easily.
I have paid DSA course from GFG. But not able to understand BIT manipulation. After watching this playlist by striver I feel the striver did it better than any other paid course in the market.
Many times I thought to comment on his post and lastly just leaving it by pressing like button.. thinking that kya kya bolega log,,! Is there anyone else like me ? Aisa koi h Banda Jo striver se bhi accha padhata ho ! I don't think so some one exist ❤
@@pranavmittal9619Bhai hai to bata do jara hum bhi Jane kon h, teacher hi na , terrorist thode h Jo bata na paoge 😂 kahi tum hi to nahi ho wo 2 cr vala Banda Jo chhup chup ke bit manipulation ka maja le rahe ho😊
@@raorao7329 bhai coder army wale rohit negi bhaiya hai hindi lanuage ke liye bas striver best hai lekin Full english me concept grasp karne me dikkat bhi aati hai or striver ka code high level ka rehta hai or rohit negi ka low level ka code lekin output same rehta
*java code* Set ith bit from last, conside 0 based indexing (10:47 ): public static void main(String[] args) { int n = 9; int k = 2; int second_desired_num = 1
there is a question on GFG : Count total set bits You are given a number N. Find the total count of set bits for all numbers from 1 to N(both inclusive). which shows TLE by all your methods can you please explain it .
What I am assuming is since we are not storing the negative answer, so 2's complement is not used. If the answer was negative, then to store it, 2's complement would have been used. This is my assumption though. Not sure
39:00 -> repeatedly removing the rightmost set bits and taking the count of times we did this operation would give us the number of set bits in a number
at 17:30 striver do the NOT operator and it flipped all the bits making it a negative number then according to full NOT operator it do 2's complement also but striver stopped at flipping can someone explain me why? edited - ok i get it why computer store binary as flipped but while showing us it do 2's complement to show us -ve binary in interger
in case of power of 2, n & (n-1) == 0 will not work if n = 0, as 0 is not a power of two, we can rather use n & (-n) == n, which mean AND n with its 2's complement it would result n, if its a power of 2
One-Liner: 1) Swapping Two Numbers : Num1=(Num1^Num2); Num2=(Num1^Num2); Num1=(Num1^Num2); 0000101 = num1 ^0001001 = num2 ________ 0001100 xor of num1 and num2 stored in num1 0001001 = num2 ----- 0000101 xor of (num1 and num2) and num2 stored in num2 0001100 ----- 0001001 2) Check If i’th bit is set or not: if (( Num &(1
At 17:20 striver is not taking 2's complement for NOT operator ? Last video he taught that if after flipping the number becomes negative , we take 2's complement , anyone please help ?
somewhere in the comments , i read "computer store binary as flipped but while showing us it do 2's complement to show us -ve binary in interger" is this right?
I think right and left shift operation or not required for finding the i th bit is set(1) or reset(0) for given binary digits Here I have code please verify it it is taking O(1) time complexity to find it.. // ith bit is set or reset import java.util.*; class SetOrReset{ public static void main(String args[]) { Scanner sc=new Scanner(System.in); String str=sc.next(); int i=1; int j=str.length()-1; int x=str.charAt(j-i)-'0'; if(x==1){ System.out.println("Set"); }else{ System.out.println("Reset"); } } }
If you find the swapping using xor confusing, then instead of xor operation use the addition and subtraction operation, it will do the job. a = 17 b = 27 a = a + b # a becomes 17 + 27 = 44 b = a - b # b becomes (17 + 27) - 27 = 44 - 27 = 17 a = a - b # a becomes (17 + 27) - 17 = 27
So in prev video, a method was taught to find ~x but it is a bit unclear. Let me try clear it up. Actually, ~x is just 1's complement of x, i.e., flip all bits. Eg: ~19 = ~(010011) = (101100) in binary = -20 in decimal Now we know (-x) is actually 2's complement of x. So what he taught is actually to find -x manually. Take prev eg, ~(010011) = (101100) in binary = -(2's complement of 101100) in decimal = -(010100) in decimal = -20 Take other way, ~(-20) = ~(101100)=010011 in binary=(directly) 19 Note: For easiness just assume that instead of 32 bits, there are only 6 bits here.
I HAVE ONE QUESTION WHEN WE ARE CHECKING IF I'th BIT IS SET OR NOT WHILE DOING RIGHT SHIFT OF NUMBER (n-1) TIMES. WOULDN'T IT CHANGES THE INPUT NUMBER SUPPLIED.
In the power of 2 case...what if the number is 0 or INT_MIN then for 0 it will be n&n-1 = 0&-1 means 0...0000 & 1...1111 its coming 0 then it will return true but actually its not power of 2 And in case of INT_MIN n&n-1 the n-1 value is getting overflowed...please solve the doubt anyone.
when we need to count the total set bits from 1 to N , the following code gives TLE when N=10^9 because of the for loop. how can this be optimised ? int count(int n) { int cnt=0; while(n!=0) { if(n&1==1) cnt++; n=n>>1; } // if(n==1) cnt++; return cnt; } int countSetBits(int n) { //Write your code here int ans=0; if(n==1) return 1; for(int i=1;i
in clearing the ith bit ques shouldnt we take -1 as while finding not of 1 its sign bit also changes in first step and so it becomes -ve and so we have to find its 2s compli
Yes , but it will work same as toggling if the bit is not set and we don't want that , if the bit will be 0 then also it will be changed to 1 if we do this.
1. Swap two numbers - 00:00
2. Check if ith bit is set or not - 3:47
3. set ith Bit - 10:47
4. clear ith Bit - 14:27
5. Toggle ith Bit - 17:52
6.Remove the last set Bit - 21:23
7. Check if a number is power of 2 or not - 28:26
8.count the number of set bits - 31:24
thanku modi ji ! abki baar 400 paar 👍
@@NAMAN-wj7dj Vote dena mt bhulna Abki baar Modi Sarkar
@@modiji8706 modi ji wo recession ka kuch hojata toh badhiya maan lgta voting m
@@02deepakmodiji khud pdh rhe hai dsa😅
RastraPati Bhawan ma A jao kl ispe wartalap krte hai
REMEMBER IF STRIVER IS MAKING , THEN IT WILL BE THE BEST PLAYLIST ON BIT MANIPULATION
Have you ever watched kunal kushwaha's videos
@@siddiqabr7110 his videos arent any good
@@aayambhatt5363 yes !! I had started my dsa journey from kunal but now shifted to striver after understanding basics of dsa.
@@aayambhatt5363I don’t understand his way of teaching
@@aayambhatt5363 His videos was once good , now it's not 😭
Never seen better teacher than u
YESS
true
One-Liner:
1) Swapping Two Numbers : Num1=(Num1^Num2);
Num2=(Num1^Num2);
Num1=(Num1^Num2);
2) Check If i’th bit is set or not: if((Num&(1
Love you bro ❤❤❤
Awesome Striver, done with sliding window and two pointers and now started with bit manipulation yesterday
Crystal clear explanation. Highly recommended for those who does not know anything about bit manipulation.
struggling so much with this topic alone. Thank you for the series!!!!
33:00 here you can simply do this
public static int countSetBit(int num){
int count = 0;
int one = 1;
while(num > 0){
if((num & one) == 1){
count++;
}
num = num >> 1;
}
return count;
}
it is almost the same thing taking the same time except you create one more variable num ;)
to clear ith bit(0 indexed), we can just do
N = n xor (1
toggle
Yes , but it will work same as toggling if the bit is not set and we don't want that , if the bit will be 0 then also it will be changed to 1 if we do this.
@@AnushkaMishra8 yeah bro
amazing video covering all concepts, soon will be mastering bit manipulations by completing your playlist.Before i used to be scared of seeing bits but now it's easy , even i started to use , today i used in one question and solved that question easily.
Best Bit Manipulation tutorial ever!!!
Thanks for starting uploading again it is very helpful for us.
the efforts this guy puts is just amazing
Sir, Your Techniques are superb
before this I thought I knew bitwise operations. But the tricks you've shown are awesome. Thanks again.
i dont know how to say thank you but you saved me striver . thank you>3000
I have paid DSA course from GFG.
But not able to understand BIT manipulation.
After watching this playlist by striver I feel the striver did it better than any other paid course in the market.
same here i paid for my gfg self paced but i'm now watching strivers youtube to solve DSA
Many times I thought to comment on his post and lastly just leaving it by pressing like button.. thinking that kya kya bolega log,,! Is there anyone else like me ? Aisa koi h Banda Jo striver se bhi accha padhata ho ! I don't think so some one exist ❤
ek h lekin me nahi batunga bas hint de deta hu : 2 crore ka package chod diya bande ne
@@pranavmittal9619Bhai hai to bata do jara hum bhi Jane kon h, teacher hi na , terrorist thode h Jo bata na paoge 😂 kahi tum hi to nahi ho wo 2 cr vala Banda Jo chhup chup ke bit manipulation ka maja le rahe ho😊
@@pranavmittal9619 who??
@@raorao7329 bhai coder army wale rohit negi bhaiya hai hindi lanuage ke liye bas striver best hai lekin Full english me concept grasp karne me dikkat bhi aati hai or striver ka code high level ka rehta hai or rohit negi ka low level ka code lekin output same rehta
*java code*
Set ith bit from last, conside 0 based indexing (10:47 ):
public static void main(String[] args) {
int n = 9;
int k = 2;
int second_desired_num = 1
The best teacher for dsa 🔥🔥
17:20 another approach (n&(INT_MAX^(1
Thanks for all these efforts :)
i just stuck to your glow in comment section 😂😂 , forgot about the lecture that is running in the background ..
This is just too good to be true bro..
Thanks a lot❤
Bhai aapka knowledge toh kamal ka hai bhai.
there is a question on GFG : Count total set bits You are given a number N. Find the total count of set bits for all numbers from 1 to N(both inclusive).
which shows TLE by all your methods can you please explain it .
Neatly, clearly explained which anyone can easily understand 😊really appreciated your efforts😊
Understood....Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
int count = 0;
int num = 7;
while(num > 0){
num = (num & (num-1));
++count;
}
print(count)
We can also do this in order to count the set bit (1)😊
17:20 when finding ~(1
same doubt bro
i think we cannot access 2's complement part and can only access negated part of the number maybe i am not sure
same doubt bro ,, I raised this on lecture one as well, but bhaiya is not replying....
Thanks for teaching every possibility answer for the problems❤❤❤
17:30 instead we can left shift 1 and use xor operators
hats off man for your hardwork
Salute to your hardwork and explanation
17:30 sir if we use not operator wouldnt the number converted into its 2's complement
same doubt. Someone please clearify
What I am assuming is since we are not storing the negative answer, so 2's complement is not used. If the answer was negative, then to store it, 2's complement would have been used. This is my assumption though. Not sure
Any solution to this I am still struggling with this.
same doubt
Same doubt .. You got the answer.
Wow this is essence of bit manipulation!!!!!!!!!! Thank you so much
Keep going 🏆
If striver is making then it will be the best playlist ;
Sir plz make more videos on sliding window
Ohh striver such an amazing lecture ..
This course was insanely good
Knowledge Packed Lecture.
39:00 -> repeatedly removing the rightmost set bits and taking the count of times we did this operation would give us the number of set bits in a number
for each problem if you write code that will better, but you already created playlist
38:00 around, using the last method
at 17:30 striver do the NOT operator and it flipped all the bits making it a negative number then according to full NOT operator it do 2's complement also but striver stopped at flipping can someone explain me why?
edited - ok i get it why computer store binary as flipped but while showing us it do 2's complement to show us -ve binary in interger
in case of power of 2, n & (n-1) == 0 will not work if n = 0, as 0 is not a power of two, we can rather use n & (-n) == n, which mean AND n with its 2's complement it would result n, if its a power of 2
To clear ith bit we can do :-
return ( n ^ (1
no we cant because 0 ^ 1 is 1 so if ith bit is already zero it will change it to 1
It is for toggle
for checking ith bit set
just do right shift by ith and check the resukting num is odd. if it is , it is set. else , not ...
MY MAN IS BACKKKKKKKKKK
Hila diye bhaiya ji 🎉🎉🎉❤❤
Set> Or
Clear/Remove -> And
Toggle -> Xor
One-Liner:
1) Swapping Two Numbers :
Num1=(Num1^Num2);
Num2=(Num1^Num2);
Num1=(Num1^Num2);
0000101 = num1
^0001001 = num2
________
0001100 xor of num1 and num2 stored in num1
0001001 = num2
-----
0000101 xor of (num1 and num2) and num2 stored in num2
0001100
-----
0001001
2) Check If i’th bit is set or not: if (( Num &(1
UNDERSTOOD 🎉🎉😁😁😁😁
At 17:20 striver is not taking 2's complement for NOT operator ?
Last video he taught that if after flipping the number becomes negative , we take 2's complement , anyone please help ?
same doubt. Please let me know, if you got the answer
understood ,thanks alot
In the clearing the set bit won't the negation of the left shift 1 make it a 2's complement and the program will add a 1 to it ?
u are the best teacher
🙏🙏TQ bhaiya for such a good explanation is topic ma smj hi ni aa raaha tha ab sb easy lg r ha
Thank you so much BHAIYA 🙏🙏🙏
W lecture. Thank you very much sir.
we can swap without using xor ?
a = a + b;
b = a - b;
a = a - b;
somewhere in the comments , i read
"computer store binary as flipped but while showing us it do 2's complement to show us -ve binary in interger"
is this right?
Python 1 liners-
=============
Swapping two numbers: a = a ^ b; b = a ^ b; a = a ^ b
Check if i'th bit is set or not: print("SET" if (Num & (1
I think right and left shift operation or not required for finding the i th bit is set(1) or reset(0) for given binary digits Here I have code please verify it it is taking O(1) time complexity to find it..
// ith bit is set or reset
import java.util.*;
class SetOrReset{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
int i=1;
int j=str.length()-1;
int x=str.charAt(j-i)-'0';
if(x==1){
System.out.println("Set");
}else{
System.out.println("Reset");
}
}
}
NICE SUPER EXCELLENT MOTIVATED
If you find the swapping using xor confusing, then instead of xor operation use the addition and subtraction operation, it will do the job.
a = 17
b = 27
a = a + b # a becomes 17 + 27 = 44
b = a - b # b becomes (17 + 27) - 27 = 44 - 27 = 17
a = a - b # a becomes (17 + 27) - 17 = 27
So in prev video, a method was taught to find ~x but it is a bit unclear. Let me try clear it up.
Actually, ~x is just 1's complement of x, i.e., flip all bits. Eg: ~19 = ~(010011) = (101100) in binary = -20 in decimal
Now we know (-x) is actually 2's complement of x. So what he taught is actually to find -x manually. Take prev eg, ~(010011) = (101100) in binary = -(2's complement of 101100) in decimal = -(010100) in decimal = -20
Take other way, ~(-20) = ~(101100)=010011 in binary=(directly) 19
Note: For easiness just assume that instead of 32 bits, there are only 6 bits here.
Can we get slides notes, @takeUforward
bro?
I HAVE ONE QUESTION WHEN WE ARE CHECKING IF I'th BIT IS SET OR NOT WHILE DOING RIGHT SHIFT OF NUMBER (n-1) TIMES. WOULDN'T IT CHANGES THE INPUT NUMBER SUPPLIED.
Great lecture.
unset the right most set bit : n&(n-1)
set the right most unset bit : n | (n+1)
super amazing!!
Thank you sir 🙏
In python you can swap without using a 3rd variable like a , b = b , a
u can do swap without using 3rd var in all languages just use a = 3, b = 7, b+=a, a = b-a, b = b-a, Output : , a = 7, b = 3,
Thank you for making this video
22:07 continue
simple superb sir
In the power of 2 case...what if the number is 0 or INT_MIN then for 0 it will be n&n-1 = 0&-1 means 0...0000 & 1...1111 its coming 0 then it will return true but actually its not power of 2
And in case of INT_MIN n&n-1 the n-1 value is getting overflowed...please solve the doubt anyone.
Thanku so much bhaiya❤❤🙏🙏🙏🙏
when we need to count the total set bits from 1 to N , the following code gives TLE when N=10^9 because of the for loop. how can this be optimised ?
int count(int n)
{
int cnt=0;
while(n!=0)
{
if(n&1==1) cnt++;
n=n>>1;
}
// if(n==1) cnt++;
return cnt;
}
int countSetBits(int n)
{
//Write your code here
int ans=0;
if(n==1) return 1;
for(int i=1;i
Great sir.❤
Any reason for using left or right shift operator what is the intuition behind it anyone
thank you anna🧡
in clearing the ith bit ques shouldnt we take -1 as while finding not of 1 its sign bit also changes in first step and so it becomes -ve and so we have to find its 2s compli
same doubt bro,, if you got the answer. Pease reply
How does JavaScript store numbers then? 😃
Thanks a lot Bhaiya
thank you sir ji
check if a number is a power of two -> !(N & 1)
Bhaiya in the Clear bit Soluton can we use XOR operation? like below
n = 13, i =2
13 -> 1101
1
use an example where the ith bit is already 0. You will get to know
Is this question available in leet code
can i use (n ^ (1
yes you can , I have also done the same for the code ninja question and it cleared all the test cases.
Yes , but it will work same as toggling if the bit is not set and we don't want that , if the bit will be 0 then also it will be changed to 1 if we do this.
Bro loves 13 anyways best lecture on yt.
Understood😊
That end music !!!
STRIVER 🤩
0 xor 0 is 1 bhaiya.. if we use xor in toggle then it might give us the wrong answer
0 xor 0 is not 1
its 0
UNDERSTOOD;
bhaiya please string start kro !!!!!!!!!!!!!!!!!!!!!
can anyone please add timestamps for all questions solved?
Understood!