Absolute Beginner's Guide to Bit Shifting
stackoverflow.com
Absolute Beginner's Guide to Bit Shifting
1–10 of 23 posts
Re: Absolute Beginner's Guide to Bit Shifting
#2Please 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).
Re: Absolute Beginner's Guide to Bit Shifting
#3In machine code language, we refer to these as rotating and shifting, instead of "shifting and non-circular shifting".
Re: Absolute Beginner's Guide to Bit Shifting
#4Please 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).
Also, although the question is tagged for "c", the top answer has some Java specific examples.
Re: Absolute Beginner's Guide to Bit Shifting
#5Please 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).
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.
Re: Absolute Beginner's Guide to Bit Shifting
#6Beyond 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.
Re: Absolute Beginner's Guide to Bit Shifting
#7Please 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).
I'm old school and it saddens me that MUL is almost as fast as SHL. DIV is still significantly slower than SHR.
Re: Absolute Beginner's Guide to Bit Shifting
#8Please 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).
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…
> 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 Finally, the practical reality for programmers is that variable-amount shifts and rotates are relatively expensive on quite a few processors.
Re: Absolute Beginner's Guide to Bit Shifting
#9This 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.
Re: Absolute Beginner's Guide to Bit Shifting
#10Please 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).
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 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.