Absolute Beginner's Guide to Bit Shifting • Hacker News Board

Re: Absolute Beginner's Guide to Bit Shifting

#11

Post by tmuir » Sun, Mar 04, 2012, 8:36 PM UTC

jiggy2011 wrote: post #6

Beyond OS kernels , drivers and embedded systems is there any real use for this? I only ask because we were never taught about bit shifting at university and I can't think of a time where it would have ever been useful in my work but despite this it seems to be a very common thing to ask about at interviews so I have sort of educated myself about it for that reason alone.

Are OS kernel, driver, and embedded systems development off topic on HN? There were several embedded developer posts in the latest Who's Hiring thread. Web development is by far the largest software segment that HN focuses on, but is by no means the only one.

Re: Absolute Beginner's Guide to Bit Shifting

#12

Post by jiggy2011 » Sun, Mar 04, 2012, 9:20 PM UTC

tmuir wrote: post #11

jiggy2011 wrote: post #6

Beyond OS kernels , drivers and embedded systems is there any real use for this? I only ask because we were never taught about bit shifting at university and I can't think of a time where it would have ever been useful in my work but despite this it seems to be a very common thing to ask about at interviews so I have sort of educated myself about it for that reason alone.

Are OS kernel, driver, and embedded systems development off topic on HN? There were several embedded developer posts in the latest Who's Hiring thread. Web development is by far the largest software segment that HN focuses on, but is by no means the only one.

I never suggested it was off topic, I usually enjoy reading the low level programming threads on HN.

I just wondered why it seems to considered something every CS grad/programmer should understand.

Re: Absolute Beginner's Guide to Bit Shifting

#13

Post by pjscott » Sun, Mar 04, 2012, 9:37 PM UTC

pm215 wrote: post #10

prophetjohn wrote: post #5

Earlier quoted context omitted.

In fact, bit shifting is always faster than anything. At the hardware level, it's just wiring; there is no logic involved in shifting the bits, so there is no propagation delay involved, unlike even the single logic gate operations like &, |, ~, etc. It's so much faster, that many compilers, for integer multiplication, will optimize these multiplications by converting them to shifts and adds. Integer division, howeve…

As well as the practical details of barrel shifter implementation design that psykotic points out, older CPUs couldn't afford the space for a barrel shifter and implemented shifts as a sequence of one-bit shifts. So for instance the 8086 took 8 clock cycles plus another 4 cycles per bit shift, and on that kind of CPU it was definitely not as fast as an addition. Incidentally there is a standard trick for integer divi…

Here's an article explaining the trick:

http://ridiculousfish.com/blog/posts/labor-of-division-episo...

And a library from the same guy for generating code at runtime to do fast division by constants:

http://libdivide.com/

Re: Absolute Beginner's Guide to Bit Shifting

#14

Post by tmuir » Sun, Mar 04, 2012, 9:42 PM UTC

jiggy2011 wrote: post #12

tmuir wrote: post #11

Earlier quoted context omitted.

Are OS kernel, driver, and embedded systems development off topic on HN? There were several embedded developer posts in the latest Who's Hiring thread. Web development is by far the largest software segment that HN focuses on, but is by no means the only one.

I never suggested it was off topic, I usually enjoy reading the low level programming threads on HN. I just wondered why it seems to considered something every CS grad/programmer should understand.

As an embedded developer/EE, I feel the same way, but from the other side. There is too much breadth for any single person to be proficient at all 7 layers, but from time to time, you still see job descriptions that ask for assembly, C, C++, Java, PHP, HTML, Python, CSS, Flash, Haskell, PCB Layout, VHDL, 7 yrs iOS...

Re: Absolute Beginner's Guide to Bit Shifting

#15

Post by spicyj » Sun, Mar 04, 2012, 9:50 PM UTC

jiggy2011 wrote: post #6

Beyond OS kernels , drivers and embedded systems is there any real use for this? I only ask because we were never taught about bit shifting at university and I can't think of a time where it would have ever been useful in my work but despite this it seems to be a very common thing to ask about at interviews so I have sort of educated myself about it for that reason alone.

> I only ask because we were never taught about bit shifting at university

At CMU, three of the first four intro programming classes discuss bit shifting in depth.

Re: Absolute Beginner's Guide to Bit Shifting

#16

Post by manvsmachine » Sun, Mar 04, 2012, 10:05 PM UTC

jiggy2011 wrote: post #6

Beyond OS kernels , drivers and embedded systems is there any real use for this? I only ask because we were never taught about bit shifting at university and I can't think of a time where it would have ever been useful in my work but despite this it seems to be a very common thing to ask about at interviews so I have sort of educated myself about it for that reason alone.

I first learned about bit-shifting when I took DIP / Computer Vision as an undergrad. All the assignments were done as plugins for ImageJ, which is apparently widely used in the scientific community (or so the course claimed). ImageJ stores the pixel values for images as bytes, ints, or longs (depending on the color-depth), so to get the individual component values from a 32-bit RGBA image (8 bits per channel), you would do something like this:

int pixel = image.get(x, y);

int alphaVal (pixel & 0xFF000000) >> 24;

int redVal = (pixel & 0x00FF0000) >> 16;

int greenVal = (pixel & 0x0000FF00) >> 8;

int blueVal = (pixel & 0x000000FF);

That's just one example w/ one piece of software, but I know similar approaches are often used within the world of imaging / graphics. Maybe networking? Seem like it would correlate well to IP address operations.

Re: Absolute Beginner's Guide to Bit Shifting

#17

Post by coldarchon » Sun, Mar 04, 2012, 10:19 PM UTC

As the question about what it does at core level is not completely answered, the difference between :2 and >> is 175 versus 6 cycles in the processor.

Re: Absolute Beginner's Guide to Bit Shifting

#18

Post by dpark » Sun, Mar 04, 2012, 10:57 PM UTC

riledhel wrote: post #2

Please don't read just the selected answer, because he got the optimizations wrong. Bit shifting operations are always faster than multiplications (as the guy with the second most voted answer explains).

You're reading it backwards.

> A good optimizing compiler will substitute shifts for multiplications when possible.

"substitute shifts for multiplications" means that multiplications will be replaced with shifts.

The wordier phrase would be "substitute with shifts for multiplications" or "substitute for multiplications with shifts".

Re: Absolute Beginner's Guide to Bit Shifting

#19

Post by Jach » Mon, Mar 05, 2012, 12:38 AM UTC

jiggy2011 wrote: post #6

Beyond OS kernels , drivers and embedded systems is there any real use for this? I only ask because we were never taught about bit shifting at university and I can't think of a time where it would have ever been useful in my work but despite this it seems to be a very common thing to ask about at interviews so I have sort of educated myself about it for that reason alone.

I bookmarked this comment since it more or less answers that question: http://news.ycombinator.com/item?id=3452869

In short, when you're dealing with a performance sensitive application they can be helpful to make it blazing fast. When you have a piece of code being executed many times they can be helpful since micro-optimizations start mattering then, too. For the same reason most of us don't write in assembly, most of us probably don't need it for our applications, we're free to waste, but besides being fun/interesting the practical applications where bit hacks can be beneficial do indeed go beyond your short-list. (Game engines (physics, graphics, AI, networking) and databases are two more general topics I can think of off the top of my head, compression is another but could just be a special case of databases.)

Re: Absolute Beginner's Guide to Bit Shifting

#20

Post by tcas » Mon, Mar 05, 2012, 1:49 AM UTC

jiggy2011 wrote: post #6

Beyond OS kernels , drivers and embedded systems is there any real use for this? I only ask because we were never taught about bit shifting at university and I can't think of a time where it would have ever been useful in my work but despite this it seems to be a very common thing to ask about at interviews so I have sort of educated myself about it for that reason alone.

I've used bit shifting a lot when dealing with any sort of audio/video applications. Specifically, when muxing audio and video into a container (i.e. MPEG transport streams) you need to set up a bunch of bit flags that are packed very tightly and also need to frequently need to write data into non-byte boundaries. The result is a couple hundred lines of code of all pointer arithmetic and bit shifts to convert between verbose data structures and the format in question.