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.
Here's the mashup (the practice problems) codeforces.com/contestInvitat...
and a pastebin with the sources and difficulties of each problem: pastebin.com/HLMw0a9q
The problems are roughly ordered by difficulty.
I currently can't find a problem on bitsets, will update the mashup if I do.
Stream will start Sunday, at the normal Codeforces round time: www.timeanddate.com/worldcloc...
I will take various questions and go over the practice problems.
Playlist of past streams: • Topic Streams
A similar, nice resource from Errichto: codeforces.com/blog/entry/73490
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

[@kushaagra098]

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

[@ColinGalen]

That did pretty well in the vote for this, so it could definitely win and be next stream's topic.

[@336_saranyamaity8]

@@ColinGalenWHere's the voting was done ?

[@ColinGalen]

@@336_saranyamaity8 It was done at ua-cam.com/video/eFlR4ymrKGI/v-deo.html
This is a special case, the voting will normally not be done via comments. That video will detail my weekly plans.

[@336_saranyamaity8]

@@ColinGalen thanks , and after commenting in most of your videos you finally replied sensei ✌️

[@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!

[@mukulkadyan7403]

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

[@godspeed5550]

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.

[@ColinGalen]

xor basis is mid-range? yikes, i'm behind
edit: a serious reply, yes, if it wins a vote

[@joshua_dlima]

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

[@rdxrdx1792]

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

[@saptarshishome4409]

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

[@harshdhawale2669]

Hey bro can you tell me from where you did learnt about bits

[@yashjoshi]

unsigned itself is wrong..
its 0 to (2^8-1)
for signed its:
-(2^7) to (2^7-1)

[@justjie1008]

Damn your explanations are godly.

[@Mani_OnFire]

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

[@josephwong2832]

you're an awesome teacher

[@shashanksingh4708]

Thanks alot this is great 👍

[@akshat2806]

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

[@ColinGalen]

FYI, I've done a dp + segtree stream, can be found at ua-cam.com/video/KX_-7AqcnEU/v-deo.html

[@akshat2806]

@@ColinGalen yeah i have seen it , i was saying like a completely different video on range queries and like some more things like graphs(advance stream ) , trees and all

[@Miyano_Shiho4869]

I have a question. For finding the k-th bit of a number x, can't we use the formula : x&(1

[@nirajandata]

thanks mr. colin

[@shahinsiddiquei4513]

AWESOME!!!

[@abdullasulfikkar5282]

Thank you :)

[@coefficient1359]

Thank you

[@georgedrooj8800]

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

[@rishisharma0930]

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

[@rajkaransingh8305]

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

[@adinonymous640]

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?

[@132abhishekanantsingh4]

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

[@williamwambua7710]

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

[@PepeTostado]

When would you use bit wise operations

[@ng3w462]

Op bro 🤟🤟

[@garvittiwari11a61]

Graphs next please 😀

[@yashjoshi]

range at 6:11 is wrong:
unsigned:
its 0 to (2^8-1)
for signed its:
-(2^7) to (2^7-1)

[@user-qt7hc9ti3o]

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

[@ScepticalKannadiga]

🔥🔥

[@vishalchoubey5606]

Binary strings next ෆ╹ .̮ ╹ෆ

[@solaris413]

next please Combinatorics 1700+

[@ColinGalen]

I'm fine with repeating stuff, but in case you (or anyone reading) didn't know, I've already done a stream on this: ua-cam.com/video/le2enQgQ7Ws/v-deo.html

[@dangduong5362]

orz

[@sobieso]

colin

[@leetcoder1159]

Yes dear

[@dioc7856]

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

[@ChandraShekhar-by3cd]

LinkedList please!

[@anshuman5554]

that's not cp