Ask HN: Help...Found a gaping hole in my low-level knowledge

[igammarays]

So I have an on-site interview in 2 weeks with a respectable hardcore software company, and part of the interview prep stuff that was given to me was this excellent article by Steve Yegge: https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions

Area 5 in the article was a wake up call, because although I've been writing code and doing web dev since I was 12, I had never heard of bitwise operators like '>>' and '^' ever in my life! I need to learn these topics, and fast, since I don't have much time for my big interview. And since I'm a person who does a lot better when I understand the underlying theory, rather than simply memorizing techniques, I would really appreciate a short book, or even articles to get me up to speed on bits, bytes and binary for a practical, low-level programmer.

Can anyone please share a short and practical guide suitable for a person who has many years experience with high level languages like Python?

[valarauca1]

XOR = Addition (without carry)

Left Shift = Multiply by 2 ^ n (without checking for overflow [1]).

Right Shift = Divide by 2 ^ n (without rounding)

As all data in stored, and processed in binary representation right/left shifts are fun hacks we gain from this system. Moving an entire integer 1 space left/right will double/halve its value! Its also very easy to replicate this operation in hardware.

Absolute Beginner Guide on S/O https://stackoverflow.com/questions/141525/absolute-beginner...

[1] Sometimes, it depends, its actually complicated, depends on language, machine, etc.

[bjourne]

Good news! It's not a hole in your knowledge. It was useful a long while ago for packing structs and efficiently multiplying and dividing by constants.

That said, you could learn a lot about the low-level by implementing an addition operation for binary strings: bin_add("10001", "111") => "11000". And if you think that's too easy try multiplication and division!

[kohanz → bjourne]

> Good news! It's not a hole in your knowledge. It was useful a long while ago

Umm, are you implying these operations aren't used present-day by developers?!

[chris_va]

I always find it useful to map a new problem into a space I am more familiar with.

Given that you have a many years of experience with high level languages, you can probably use array algorithms as an analogue for bitwise operations.

Can you shift the elements of an array left, right? Intersect/union two of them? Count the true/false values? Bit level operations are just a special case that CPUs do very efficiently, and happen to be quite useful for a wide set of algorithms.

It is useful to understand how CPUs represent bits (little/big endian, float encoding), and look at a couple of algorithms that take advantage of that (e.g. why multiplying by 2 on a computer is a cheaper operation than multiplying by a random number).

[lingua_franca]

https://graphics.stanford.edu/~seander/bithacks.html

[jimkri → lingua_franca]

I second this website. It has everything that you will need. Also OP if you need practice questions I have all of my past exams from my Low Level Programming class that has tons of Bit wise operator questions.

[chewxy]

There is a fantastic book - Hacker's Delight. Read it. Love it.

[kelukelugames]

Buy Gayle's book and read through the bit operator questions.