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

3 жыл бұрын

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!

These lectures are incredible. Thanks for sharing.

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

Amazing, all of the methods are toward optimizing a program.

This is just so awesome! Thank you very much.

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

Interesting lecture. Thanks a lot.

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

3 жыл бұрын

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

2 жыл бұрын

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

Жыл бұрын

@@deansmith4752 Still should be exposed to students so they know as an exercise in the least.

@lembueno894

Жыл бұрын

you are worse hitler if you make a course harder becuase it was easier for you

0b is not indicating boolean it simply means the number is binary

@aritradattagupta9181

Жыл бұрын

And binary is essentially boolean.

@farhadzada3162

6 ай бұрын

😂😂😂😂 when you don't know that you don't know

Thank you sooo much!

Exercise solution: popcount(x - 1)

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

3 жыл бұрын

It's a binary constant

@kewtomrao

Жыл бұрын

I guess boolean in the sense each bit are either a one or a zero?

@bettercalldelta

10 ай бұрын

"binary constant" would be more correct

would help if backed with actual runtime flags and settings (thinking of merge subroutine)

At 37:40 you can perform the modulus using (x+y) & (n-1) if n is a power of 2 btw

@saicharanmarrivada5077

3 ай бұрын

Compiler automatically does that

역시 MIT 강의…

this is the coolest thing in the world

The size of C in the merge function is unknown so that might create a segfault.

37:40 could the last line not become: r = z - n * (z >= n) ? Or is & faster than multiplication?

1:50 I have to assume they mean a "binary constant", calling a bitstring a "boolean constant" just seems weird.

@shivamjalotra7919

3 жыл бұрын

Yeah it just stands to denote that the number is a binary number. I wonder what the 0 in "0b" stands for ?

@elliotwaite

3 жыл бұрын

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

3 жыл бұрын

@@elliotwaite Hmm makes sense, but why zero any not any other number ?

@elliotwaite

3 жыл бұрын

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

3 жыл бұрын

Boolean constant because it's either "on" or "off" represented by "1" or "0"

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.

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.

at some point in the lecture does he talk about floats?

Is the deBruijn sequence trick worth it? why not shift right till we find one while counting shifts?

@bettercalldelta

10 ай бұрын

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.

I dont understand how right & (1

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( 01( 0(< carry 1)000 = 1000

This seems to be a preparatory course for the "Obfuscated C Contest" 😉😁

the bits scare me (it went 0 to 100 from queens problem)

How would I toggle the whole string

@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.

I do not understand that no temp swap O.O I'll remember it for the future though

@yashas9974

2 жыл бұрын

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

2 жыл бұрын

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

2 жыл бұрын

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

2 жыл бұрын

@@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.

30:00

2:11

I guess we just need to know these things and then that's enough,never use this in the project

"Don't use any of this, you will mess with the compiler and it is better at optimizing than you"

@shivamjalotra7919

3 жыл бұрын

That's the sanest advice for this video. I wonder if real developers ever define min(a, b) = b ^ ((a ^ b) & -(a < b)) !

@jeffpowell860

3 жыл бұрын

@@shivamjalotra7919 nah they just go min(a,b) using a built in function lol

@yashas9974

2 жыл бұрын

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

2 жыл бұрын

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.

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

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.

To me most magic stuff seem meaningless unless explained how they're done.

10:35 drink up

t2eel