Bitwise Operations for Competitive Programming | Topic Stream 8

Bitwise operations - binary representation in general, the operations that can be done on binary numbers (both logical and bitwise), and some problemsolving techniques involving them. Feel free to use the timestamps to skip around to what you don't know, I started from a very basic level.

The problems are roughly ordered by difficulty.

I currently can't find a problem on bitsets, will update the mashup if I do.

I will take various questions and go over the practice problems.

Timestamps:
Intro + what is binary? 00:00
Binary representation in computers 04:49
Bitwise and logical operations (and, xor, etc.) 07:00
Builtin functions (popcount, etc.) 21:15
Some tricks/identities 26:32
Using bitmasks, bitsets, bitmask DP 31:34
Main takeaways for problemsolving 39:46

[kushaagra]

This is actually amazing! Can you do number theory next? I am really looking forward to it!!!

[ImSaneperson]

Small correction at 6:11 that will be from -(2^7) to (2^7 - 1 ) for 8 bits signed integer .

[rdxrdx]

I don't know whether you are still active, but after 2 years it still helped me

[godspeed]

Thanks for the mashup and stream!! Also would really appreciate if you could cover topics in the future required for mid range participants. For ex, Grundy games, Xor Basis, probably harder adhoc problems, etc. Just harder problems in general. Really liked the dp optimization video.

[supersaiyan-goku-san]

Thanks for starting it out from scratch, I'm a noob but i was actually able to wrap my head and get a fairly decent understanding!

The example problems given in between in the video to think are very helpful, i was able to arrive at the solution myself and that led to getting some confidence in the topic as well! Thank you!

[mukulkadyan]

Started following u after those precious topic streams and they are back now 😍😍Thanks alot @Colin

[adinonymous]

At the 38:00 minute mark, why is the complexity or number of transitions = 3^n? The transitions mentioned are conditional on the bit in the original number, right? If that bit is 0, then the submask is forced to have 0 - if the bit is 1, then the submask can have either 0 or 1 - but basically there's only 1 OR 2 transitions possible at any state.

Then why do we have 3^n, implying 3 transitions at every state?

[joshua_dlima]

Amazing vid bro!!! one of the best vids on bit manipulation out there! tysm!!

[yashjoshi]

range at 6:11 is wrong:

unsigned:
its 0 to (2^8-1)

for signed its:
-(2^7) to (2^7-1)

[akshat]

These are just incredible plz keep doing some complex topics like types of dp, segtree

[rishisharma]

Bits are independent....Wow, it made approaching problems easier

[StopRemindingMeOfThoseDays]

I have a question. For finding the k-th bit of a number x, can't we use the formula : x&(1 << k)? Great video by the way

[Mani_OnFire]

Thank you so much bro, very very very useful, I'm very happy, I'm very thankful very much, peace ✌️

[rajkaransingh]

Can you shed light on monotonic nature of AND and OR or share some resources regarding this

[georgedrooj]

How many days do we have to solve the mashup ?? To stick with your plan

[SUJALCHAUHAN-cc]

here you said 3^n but there are many duplicates so what is the correct

[totallyoverdosed]

btw what's the time complexity of _popcount, _clz and _ctz

[PepeTostado]

When would you use bit wise operations

[williamwambua]

Would actually appreciate if we picked couple problems and we implement them...Thank you

[dioc]

Not my point to cpmplain but wathcing this viedo made me watch also 20+ ads wtf