3. Bit Hacks

MIT 6.172 Performance Engineering of Software Systems, Fall 2018
Instructor: Julian Shun

Prof. Shun discusses an array of bit hacks and discusses the types of hacks compilers do and bit hacks to do by hand when the compiler doesn't optimize.

License: Creative Commons BY-NC-SA

[dengan]

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<<k); )
12:17 Clear the k-th bit ( y= x & ~(1<<k); )
12:50 Toggle the k-th bit ( y= x ^ (1<<k); )
13:17 Extract a bit field ( (x & mask)>>shift; )
14:29 Set a bit field ( x = (x & ~mask) | (y<<shift); )
17:09 No-temp swap (triple XOR)
24:00 No-branch minimum ( r= y ^ ((x^y) & -(x<y)); )
25:20 Application of no-branch minimum to merging of 2 sorted arrays (branch-less version at 31:50)
37:46 Branch-less modular addition
38:24 Round-up to a power of 2
42:39 Compute the mask of the least significant 1 ( r= x & (-x); )
43:43 * Compute log(x) where x is power of 2
45:30 * Mathemagical trick
51:06 * Why it works: de Bruijn sequences
59:42 N-Queens problem in chess
1:08:15 * Count the number of 1 bits in a word x: simplest solution
1:10:06 * Memory-bound solution
1:12:00 * Parellel divide-and-conquer solution: O(Lg w)
1:18:16 Further reading

[kptczdq]

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!

[steveotieno]

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

[graczmisiek]

This is awesome and easy to follow. 21:52 Another AB swap without a temp variable
a = 5
b = 3
a = (a << 8) | b
b = a >> 8
a = a & 0xf

[bertalankormendy]

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

[charlesbradshaw]

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

[miketag]

These lectures are incredible. Thanks for sharing.

[adamglustein]

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

[allandogreat]

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

[cipriancimpan]

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?

[PRUTHVIRAJRGEEB]

This is just so awesome! Thank you very much.

[cacheman]

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

[djupstaten]

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

[patrickbg]

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

[awsumpersun]

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

[_Stin_]

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.

[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

[TranscendentBen]

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.

[tibiaward]

this is the coolest thing in the world

[vado]

I dont understand how right & (1 << (n-1-r+c)) checks for the diagonal