3. Bit Hacks

  Рет қаралды 67,179

MIT OpenCourseWare

MIT OpenCourseWare

Күн бұрын

Пікірлер: 71
@dengan699
@dengan699 4 жыл бұрын
2:11 Binary representation of (un)signed integers 4:44 Complementary relationship (-x = ~x+1) 7:21 Hex representation 8:31 Basic Bitwise operations 11:03 Set the k-th bit ( y= x | (1
@leixun
@leixun 4 жыл бұрын
Thanks!
@UbiycaCrabov
@UbiycaCrabov 7 ай бұрын
If you don't understand how the three XOR trick works( 19:20 ), try drawing Euler circles. Two circles are like the numbers A and B. The place where they do not match is XOR, where they match is & . After doing this operation 2 more times as in the lecture, you will get the result. Good luck!
@bertalankormendy908
@bertalankormendy908 3 жыл бұрын
In the comments: bit tricks don’t matter, how to compile, etc In the video: a person in a onesie performing a “magic” trick with volunteers
@graczmisiek4131
@graczmisiek4131 2 жыл бұрын
This is awesome and easy to follow. 21:52 Another AB swap without a temp variable a = 5 b = 3 a = (a > 8 a = a & 0xf
@steveotieno8441
@steveotieno8441 5 жыл бұрын
I am a third year student doing info-tech and each time I watch these lectures from MIT I'm taken amazed at 2 things 1. The lucidity of the tutors, and; 2. The fact that I have only met like only 10% of the content I hear from you guys in my university I kind of get the idea that you guys are telling me i have a lot of work to do and a long way to go. and am also thinking Should I kind of ask my university to change the syllabus or the lecturers???
@techgamer1333
@techgamer1333 4 жыл бұрын
Cause they have a little knowledge and experience about the course and not knowing what to tech and what to not and ,coming up with a messy lecture in everyday and giving us with no real life examples where we can implement our knowledge to grow more , right? . I totally agree with u.
@deansmith4752
@deansmith4752 3 жыл бұрын
These are bit hacks, as a result will complicate your teaching and can be very platform and compiler dependent. Get the code working, efficiency comes later.
@johnyepthomi892
@johnyepthomi892 2 жыл бұрын
@@deansmith4752 Still should be exposed to students so they know as an exercise in the least.
@lembueno894
@lembueno894 Жыл бұрын
you are worse hitler if you make a course harder becuase it was easier for you
@adamglustein8700
@adamglustein8700 11 ай бұрын
At 37:40 you can perform the modulus using (x+y) & (n-1) if n is a power of 2 btw
@saicharanmarrivada5077
@saicharanmarrivada5077 10 ай бұрын
Compiler automatically does that
@CosmiaNebula
@CosmiaNebula 2 жыл бұрын
Exercise solution: popcount(x - 1)
@nteasushz
@nteasushz 3 жыл бұрын
These lectures are incredible. Thanks for sharing.
@SphereofTime
@SphereofTime 2 ай бұрын
11:45 problem. Set kth bit in a word to 1. Idea;shift and OR
@PRUTHVIRAJRGEEB
@PRUTHVIRAJRGEEB 4 жыл бұрын
This is just so awesome! Thank you very much.
@charlesbradshaw1285
@charlesbradshaw1285 3 жыл бұрын
0b is not indicating boolean it simply means the number is binary
@aritradattagupta9181
@aritradattagupta9181 Жыл бұрын
And binary is essentially boolean.
@farhadzada3162
@farhadzada3162 Жыл бұрын
😂😂😂😂 when you don't know that you don't know
@allandogreat
@allandogreat 3 жыл бұрын
Amazing, all of the methods are toward optimizing a program.
@SphereofTime
@SphereofTime 2 ай бұрын
17:03 no temp swap in bit
@SphereofTime
@SphereofTime 2 ай бұрын
15:46 set a bit field
@cipriancimpan9942
@cipriancimpan9942 3 жыл бұрын
Anyone knows why the teacher referring to the `0b` prefix as a `boolean constant`? It seemed counter-intuitive, since `0x` refers to the hexadecimal system - so I looked it up and it seems '0b' is used to represent a base-2 number. So I wonder, why `boolean constant` - because its values can be only 0 & 1, like booleans?
@XeartyBG
@XeartyBG 3 жыл бұрын
It's a binary constant
@kewtomrao
@kewtomrao 2 жыл бұрын
I guess boolean in the sense each bit are either a one or a zero?
@bettercalldelta
@bettercalldelta Жыл бұрын
"binary constant" would be more correct
@SphereofTime
@SphereofTime 2 ай бұрын
17:43 no temp swap
@cacheman
@cacheman 4 жыл бұрын
1:50 I have to assume they mean a "binary constant", calling a bitstring a "boolean constant" just seems weird.
@shivamjalotra7919
@shivamjalotra7919 4 жыл бұрын
Yeah it just stands to denote that the number is a binary number. I wonder what the 0 in "0b" stands for ?
@elliotwaite
@elliotwaite 4 жыл бұрын
@@shivamjalotra7919, I think the zero is there to distinguish it from potential identifiers (like variables or function names) since identifiers can't start with a number.
@shivamjalotra7919
@shivamjalotra7919 4 жыл бұрын
@@elliotwaite Hmm makes sense, but why zero any not any other number ?
@elliotwaite
@elliotwaite 4 жыл бұрын
@@shivamjalotra7919, I think because you usually don't start an integer with a zero, so it helps distinguish it. And octal literals, which only use a single zero prefix and no letter, wouldn't work with any other leading number. The octal value of 010 is equal to 8.
@lebohangkuenane323
@lebohangkuenane323 3 жыл бұрын
Boolean constant because it's either "on" or "off" represented by "1" or "0"
@sirgregoryadams
@sirgregoryadams Жыл бұрын
5:18 - "the right-most 0 bit"? Isn't it that you just adding 1 to lowest order bit is 1 + 1 = 10 i.e. 0 => "carry 1" and that then propagates/repeats all the way to the 4th lowest order bit, where 0 + 1 is then 1? 0111 + 0001 => 011(< carry 1)0 => 01(< carry 1)00 => 0(< carry 1)000 = 1000
@patrickbg110
@patrickbg110 9 ай бұрын
37:40 could the last line not become: r = z - n * (z >= n) ? Or is & faster than multiplication?
@amirkhan355
@amirkhan355 4 жыл бұрын
Thank you sooo much!
@sanjaygatne1424
@sanjaygatne1424 3 жыл бұрын
Interesting lecture. Thanks a lot.
@awsumpersun321
@awsumpersun321 3 жыл бұрын
would help if backed with actual runtime flags and settings (thinking of merge subroutine)
@_Stin_
@_Stin_ 3 жыл бұрын
IMHO, I wouldn't recommend using 'x' and 'y' to identify bits if you're using the name 'XOR', it gets confusing after a while ;) I used to use EOR, too.
@nguyenkien5558
@nguyenkien5558 2 жыл бұрын
역시 MIT 강의…
@SphereofTime
@SphereofTime 2 ай бұрын
34:01 machine compolet optimizinh
@Tau-qr7f
@Tau-qr7f Жыл бұрын
Is the deBruijn sequence trick worth it? why not shift right till we find one while counting shifts?
@bettercalldelta
@bettercalldelta Жыл бұрын
The branched algorithm "while (x >>= 1) y++;" with y = floor(log2(x)) is more practical in most contexts, however sometimes there is a need for branchless algorihtms.
@tibiaward5555
@tibiaward5555 3 жыл бұрын
this is the coolest thing in the world
@djupstaten2328
@djupstaten2328 7 ай бұрын
The size of C in the merge function is unknown so that might create a segfault.
@pschneider1968
@pschneider1968 2 жыл бұрын
This seems to be a preparatory course for the "Obfuscated C Contest" 😉😁
@vado4003
@vado4003 Жыл бұрын
I dont understand how right & (1
@jeffpowell860
@jeffpowell860 4 жыл бұрын
"Don't use any of this, you will mess with the compiler and it is better at optimizing than you"
@shivamjalotra7919
@shivamjalotra7919 4 жыл бұрын
That's the sanest advice for this video. I wonder if real developers ever define min(a, b) = b ^ ((a ^ b) & -(a < b)) !
@jeffpowell860
@jeffpowell860 4 жыл бұрын
@@shivamjalotra7919 nah they just go min(a,b) using a built in function lol
@yashas9974
@yashas9974 3 жыл бұрын
@@shivamjalotra7919 Not only do people not use such tricks in production code, it's also slower. The branched minimum can be reduced to a conditional move on architectures supporting them (x86). You will have a three instruction sequence for `min` on x86: cmp a, b ; sets the flags depending on the result of b - a mov result, b ; assume 'b' is the minimum and move it to 'result' cmovle result, a ; move 'a' to 'result' if 'a < b` is true (the flags have been set in the cmp instruction) The instruction sequence for `b ^ ((a ^ b) & -(a < b))` will contain significantly more number of instructions with at least four dependencies. It's several times slower than the conditional move based solution.
@yashas9974
@yashas9974 3 жыл бұрын
Futhermore, compilers today will optimize `(a < b) ? a : b` to a conditional move. They will also "optimize" the trick `b ^ ((a ^ b) & -(a < b))` to a conditional move. Yes, the trick, normal ternary operator based min and the min function will all generate the exact same optimized machine code.
@AkamiChannel
@AkamiChannel 3 жыл бұрын
at some point in the lecture does he talk about floats?
@TranscendentBen
@TranscendentBen 3 жыл бұрын
For a moment I wondered why processors don't have max and min instructions, but then he mentions cmove - you can do the same with compare and cmove. I recall some (much) older processors (was it DG Nova?) had a conditional skip-next-instruction instruction, which would be (often, when it's not a jump instruction you're skipping - IIRC it did NOT have a conditional jump instruction so this method was used for branching) ideal for not blowing the speculative execution thing, but that relied on all instructions being the same length. Then again, with all the other things modern processors do, it would already know the length of the instruction it would be skipping. These things are so much more complicated (and amazingly faster) than when I was in college.
@ASCENDANTGAMERSAGE
@ASCENDANTGAMERSAGE 3 жыл бұрын
I do not understand that no temp swap O.O I'll remember it for the future though
@yashas9974
@yashas9974 3 жыл бұрын
Memory trick: There are three assignments. The expression on right-hand side of all the assignments is the XOR of both operands. The left-hand side can be any alternating sequence of the operands: x -> y -> x OR y -> x -> y. x = x ^ y y = x ^ y x = x ^ y Let's convert this to SSA form. x1 = x ^ y y1 = x1 ^ y x2 = x1 ^ y1 Now substitute the expression for x1. x1 = x ^ y y1 = (x ^ y) ^ y x2 = (x ^ y) ^ y1 Now substitute expression for y1. x1 = x ^ y y1 = (x ^ y) ^ y x2 = (x ^ y) ^ (x ^ y) ^ y Note that XOR is commutative. Simplify the expressions by noting that XOR is the inverse of itself: x ^ y ^ y = x. Why is XOR the inverse of itself? You can understand XOR in multiple ways: 1. XOR gives a mask where the bits in the two operands differ 2. XOR toggles bits in one of the operand at positions where there is 1 in the other operand; otherwise, it leaves the bit unchanged. You can now imagine the first (x ^ y) to give the bit string where bits differ. Now you're XORing it with `y`. In essence, you're flipping bits of `y` where it differs with `x`. This leaves you with `x`. Another way to think about this is that (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x. According to interpretation 2, XOR toggles bits in x where the bits are one in the second operand. Since the second operand is zero, it doesn't toggle any bit which gives x ^ 0 as x (as nothing was flipped). Simplifying the expressions that were earlier using the above rules, you can reduce it to the following: x1 = x ^ y y1 = (x ^ y) ^ y = x ^ (y ^ y) = x ^ 0 = x x2 = (x ^ y) ^ (x ^ y) ^ y = (x ^ x) ^ (y ^ y) ^ y = 0 ^ 0 ^ y = 0 ^ y = y At the end, you have y1 = x and x2 = y. These are what are assigned to `x` and `y` at the end.
@constantijndekker8343
@constantijndekker8343 3 жыл бұрын
If you don’t understand it, it’s best to just forget about it because it’s only useful to obscure your code for anyone reading it.
@yashas9974
@yashas9974 3 жыл бұрын
@@constantijndekker8343 I disagree. There are a few fundamental properties of XOR it teaches. It's a very good illustrative example. I agree that it has no use in production code.
@constantijndekker8343
@constantijndekker8343 3 жыл бұрын
@@yashas9974 Yeah well I suppose it’s nice to know some properties about the xor-operator, which can be explored when learning this trick. If that’s what OP meant with “remember for the future” that’s not at all bad. But I was interpreting “remember for future use” which is not a good idea.
@AviPars
@AviPars 2 жыл бұрын
How would I toggle the whole string
@razzokk
@razzokk 2 жыл бұрын
You can toggle a whole bitstring like this: `x = x ^ -1`; You could see the xor as an activatable toggle, and with -1 (all bits set) we activate the toggle for each bit. If we say that xor is of form `x = a ^ b` and `a` is the bit we want to toggle than `b` can be seen as a switch that says if we actually toggle or not. If `b` is set than we toggle the input bit a. To illustrate this, lets take a look at what happens if `b` is not set: `0 ^ 0 = 0` and `1 ^ 0 = 1`; we can see that in both instances x = a. Lets look at what happens when `b` is set: `0 ^ 1 = 1` and `1 ^ 1 = 0` so x = !a. You can extend this to any length of a bitstring.
@norliegh
@norliegh Жыл бұрын
the bits scare me (it went 0 to 100 from queens problem)
@Spark_T_ai
@Spark_T_ai 10 ай бұрын
30:00
@SphereofTime
@SphereofTime 2 ай бұрын
6:17 hex
@AviPars
@AviPars 2 жыл бұрын
10:35 drink up
@zhaobryan4441
@zhaobryan4441 3 жыл бұрын
I guess we just need to know these things and then that's enough,never use this in the project
@gadisasabri2056
@gadisasabri2056 4 жыл бұрын
2:11
@imumaru4023
@imumaru4023 Жыл бұрын
How come n oone is asking about how the magic trick word xD. I am totally flabbergasted by the trick and I really wish to know how it actually works
@ramiadel5589
@ramiadel5589 4 жыл бұрын
t2eel
4. Assembly Language & Computer Architecture
1:17:35
MIT OpenCourseWare
Рет қаралды 733 М.
9. What Compilers Can and Cannot Do
1:18:46
MIT OpenCourseWare
Рет қаралды 78 М.
“Don’t stop the chances.”
00:44
ISSEI / いっせい
Рет қаралды 62 МЛН
Арыстанның айқасы, Тәуіржанның шайқасы!
25:51
QosLike / ҚосЛайк / Косылайық
Рет қаралды 700 М.
We Attempted The Impossible 😱
00:54
Topper Guild
Рет қаралды 56 МЛН
17. Synchronization Without Locks
1:20:10
MIT OpenCourseWare
Рет қаралды 33 М.
Bit Manipulation
34:20
Make School
Рет қаралды 61 М.
15. Cache-Oblivious Algorithms
1:21:47
MIT OpenCourseWare
Рет қаралды 10 М.
12. Parallel Storage Allocation
1:17:21
MIT OpenCourseWare
Рет қаралды 11 М.
Algorithms: Bit Manipulation
9:06
HackerRank
Рет қаралды 541 М.
Fast Inverse Square Root - A Quake III Algorithm
20:08
Nemean
Рет қаралды 5 МЛН
2. Bentley Rules for Optimizing Work
1:20:10
MIT OpenCourseWare
Рет қаралды 72 М.
MATH 4800-001 FALL 2024 - Week 14 - Invariant Measures 3
1:11:17
“Don’t stop the chances.”
00:44
ISSEI / いっせい
Рет қаралды 62 МЛН