6 ms·

Absolute Beginner's Guide to Bit Shifting

101 points by ksetyadi 15y ago

riledhel 15y ago
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).
- _bbs 15y ago
  Also, although the question is tagged for "c", the top answer has some Java specific examples.
- prophetjohn 15y ago
  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, however, usually just involves a lookup table.
  - psykotic 15y ago
    > In fact, bit shifting is always faster than anything. This is overly simplistic. A fixed bitwise mapping is simple wiring and about as fast as anything can be, yes. Extending that, the "fastest" 32-bit shifter might be to put down 31 circuits, one for each possible shift amount. But that still requires a mux tree to select between the different circuits, which already goes beyond simple wiring. While that might be the minimum-delay implementation, it's also very area inefficient. A more area-efficient design would be to cascade lg(32) = 5 muxed shifters, one for each bit in the shift amount. For example, x << 19 is the same as ((x << 16) << 2) << 1. If you read a VLSI design textbook, you'll see that there are all kinds of low-level tricks for designing barrel shifters, especially when it comes to layout. Finally, the practical reality for programmers is that variable-amount shifts and rotates are relatively expensive on quite a few processors.
  - pm215 15y ago
    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 division by constant which allows you to convert it into a series of 3 to 5 shift and add/subtract operations; any decent C compiler will implement this. _Hacker's Delight_ has the explanation of the algorithm, I think.
    - pjscott 15y ago
      Here's an article explaining the trick: http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html 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/ http://libdivide.com/
- losethos 15y ago
  I'm old school and it saddens me that MUL is almost as fast as SHL. DIV is still significantly slower than SHR.
- dpark 15y ago
  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".
hackermom 15y ago
In machine code language, we refer to these as rotating and shifting, instead of "shifting and non-circular shifting".
jiggy2011 15y ago
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.
- tmuir 15y ago
  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.
  - jiggy2011 15y ago
    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.
    - tmuir 15y ago
      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...
- spicyj 15y ago
  > 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.
- manvsmachine 15y ago
  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.
swordswinger12 15y ago
This could've helped me last week. I was pulling my hair out debugging a CUDA implementation of the SHA3 candidate BLAKE, and after a full week of debugging the same 70 lines (and one complete rewrite) the issue turned out to be most-significant-bit padding with arithmetic right shifts. I just changed every 'char' type to 'uint8_t' and the code worked perfectly.
coldarchon 15y ago
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.

101 points by ksetyadi 15y ago

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

_bbs 15y ago
Also, although the question is tagged for "c", the top answer has some Java specific examples.
prophetjohn 15y ago
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, however, usually just involves a lookup table.
- psykotic 15y ago
  > In fact, bit shifting is always faster than anything. This is overly simplistic. A fixed bitwise mapping is simple wiring and about as fast as anything can be, yes. Extending that, the "fastest" 32-bit shifter might be to put down 31 circuits, one for each possible shift amount. But that still requires a mux tree to select between the different circuits, which already goes beyond simple wiring. While that might be the minimum-delay implementation, it's also very area inefficient. A more area-efficient design would be to cascade lg(32) = 5 muxed shifters, one for each bit in the shift amount. For example, x << 19 is the same as ((x << 16) << 2) << 1. If you read a VLSI design textbook, you'll see that there are all kinds of low-level tricks for designing barrel shifters, especially when it comes to layout. Finally, the practical reality for programmers is that variable-amount shifts and rotates are relatively expensive on quite a few processors.
- pm215 15y ago
  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 division by constant which allows you to convert it into a series of 3 to 5 shift and add/subtract operations; any decent C compiler will implement this. _Hacker's Delight_ has the explanation of the algorithm, I think.
  - pjscott 15y ago
    Here's an article explaining the trick: http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html 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/ http://libdivide.com/
losethos 15y ago
I'm old school and it saddens me that MUL is almost as fast as SHL. DIV is still significantly slower than SHR.
dpark 15y ago
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".

hackermom 15y ago

In machine code language, we refer to these as rotating and shifting, instead of "shifting and non-circular shifting".

jiggy2011 15y ago

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.

tmuir 15y ago
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.
- jiggy2011 15y ago
  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.
  - tmuir 15y ago
    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...
spicyj 15y ago
> 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.
manvsmachine 15y ago
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.

swordswinger12 15y ago

This could've helped me last week. I was pulling my hair out debugging a CUDA implementation of the SHA3 candidate BLAKE, and after a full week of debugging the same 70 lines (and one complete rewrite) the issue turned out to be most-significant-bit padding with arithmetic right shifts. I just changed every 'char' type to 'uint8_t' and the code worked perfectly.

coldarchon 15y ago

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.