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!
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???
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.
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.
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?
@@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, 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.
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
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.
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.
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.
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 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.
@@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.
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.
Yes coding is the life for me. I'm going to love this career. Computer Science is very interesting to me. I want to get a PhD in Computer Science and become a College Professor too. I'm working on a BS in Computer Science at SNHU.EDU online I'm a Freshmen.
@@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.
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.
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
Thanks!
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!
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???
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.
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.
@@deansmith4752 Still should be exposed to students so they know as an exercise in the least.
you are worse hitler if you make a course harder becuase it was easier for you
Exercise solution: popcount(x - 1)
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
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
0b is not indicating boolean it simply means the number is binary
And binary is essentially boolean.
😂😂😂😂 when you don't know that you don't know
At 37:40 you can perform the modulus using (x+y) & (n-1) if n is a power of 2 btw
Compiler automatically does that
15:46 set a bit field
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?
It's a binary constant
I guess boolean in the sense each bit are either a one or a zero?
"binary constant" would be more correct
These lectures are incredible. Thanks for sharing.
11:45 problem. Set kth bit in a word to 1. Idea;shift and OR
17:43 no temp swap
17:03 no temp swap in bit
Amazing, all of the methods are toward optimizing a program.
The size of C in the merge function is unknown so that might create a segfault.
1:50 I have to assume they mean a "binary constant", calling a bitstring a "boolean constant" just seems weird.
Yeah it just stands to denote that the number is a binary number. I wonder what the 0 in "0b" stands for ?
@@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.
@@elliotwaite Hmm makes sense, but why zero any not any other number ?
@@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.
Boolean constant because it's either "on" or "off" represented by "1" or "0"
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
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.
37:40 could the last line not become:
r = z - n * (z >= n)
?
Or is & faster than multiplication?
would help if backed with actual runtime flags and settings (thinking of merge subroutine)
This is just so awesome! Thank you very much.
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.
I dont understand how right & (1
at some point in the lecture does he talk about floats?
This seems to be a preparatory course for the "Obfuscated C Contest" 😉😁
Is the deBruijn sequence trick worth it? why not shift right till we find one while counting shifts?
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.
Interesting lecture. Thanks a lot.
역시 MIT 강의…
the bits scare me (it went 0 to 100 from queens problem)
this is the coolest thing in the world
I do not understand that no temp swap O.O I'll remember it for the future though
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.
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.
@@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.
@@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.
How would I toggle the whole string
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.
Thank you sooo much!
Yes coding is the life for me. I'm going to love this career. Computer Science is very interesting to me. I want to get a PhD in Computer Science and become a College Professor too. I'm working on a BS in Computer Science at SNHU.EDU online I'm a Freshmen.
I guess we just need to know these things and then that's enough,never use this in the project
34:01 machine compolet optimizinh
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
6:17 hex
30:00
"Don't use any of this, you will mess with the compiler and it is better at optimizing than you"
That's the sanest advice for this video. I wonder if real developers ever define min(a, b) = b ^ ((a ^ b) & -(a < b)) !
@@shivamjalotra7919 nah they just go min(a,b) using a built in function lol
@@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.
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.
10:35 drink up
2:11
t2eel