Which real use cases exist for arithmetic right bit shifting?

Question

I stumbled upon a question that asks whether you ever had to use bit shifting in real projects. I have used bit shifts quite extensively in many projects, however, I never had to use arithmetic bit shifting, i.e., bit shifting where the left operand could be negative and the sign bit should be shifted in instead of zeros. For example, in Java, you would do arithmetic bit shifting with the >> operator (while >>> would perform a logical shift). After thinking a lot, I came to the conclusion that I have never used the >> with a possibly negative left operand.

As stated in this answer arithmetic shifting is even implementation defined in C++, so – in contrast to Java – there is not even a standardized operator in C++ for performing arithmetic shifting. The answer also states an interesting problem with shifting negative numbers that I was not even aware of:

+63 >> 1 = +31 (integral part of quotient E1/2E2)
00111111 >> 1 = 00011111
-63 >> 1 = -32 
11000001 >> 1 = 11100000

So -63>>1 yields -32 which is obvious when looking at the bits, but maybe not what most programmers would anticipate on first sight. Even more surprising (but again obvious when looking at the bits) is that -1>>1 is -1, not 0.

So, what are concrete use cases for arithmetic right shifting of possibly negative values?

Vaasta

But wait, >> is the arithmetic shift. >>> is the logical shift. – Nocuous

@harold: Oh right, thanks, corrected – Vaasta

@Close votes: The question I cited on top got 47 up votes, no down votes and is even community wiki. My question basically ask the same thing, only in a more narrowed context. Hence, I do not think this question is opinion based, it just asks for a use case for something. – Vaasta

That questions is old though. These days everything gets voted to close. Btw, arithmetic shift is useful to turn a bit into a full-width mask in some cases. – Nocuous

@harold: Could you explain that one-bit to mask thingy? Maybe it is even worth an answer, even if you haven't used it in a real project, yet. – Vaasta

Division by two happens a lot (avaraging). From C I know the usage; but more like show-off, practising ones knowledge, rather than undertaxing the compiler's optimization. And then there is assembler. – Honig

@JoopEggen: But on negative numbers, shifting right is not division by 2! See my example. -63>>1 is -32, not -31! – Vaasta

Strangely enough, your example is also not "division by 2". Easiest proven by reverting the operation: 2 times -31 is not -63 again. – Languet

@Jongware: It is int division by two, i.e., what you get when you do a/2 with a being an integral type in almost all programming languages. – Vaasta

There's an example in https://mcmap.net/q/14898/-why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array – Nocuous

@Vaasta yes -3 >> 1 = -2. But if (2n+1)/2 = n then for n = -2 it fits. I however vaguely remember a solved bug in standard java involving >>, binary search? – Honig

@JoopEggen yes it was solved by turning the >> into a >>> though, so it's really an example of when not to use >> – Nocuous

I've implemented the algorithm of Stein (binary gcd algorithm) using the approach described by Knuth (TAOCP §4.5.2 algorithm B) with an extra modification so it uses the ffs() function and an arithmetic right shift instead of repeated division-by-two. – Unwarranted

>> on signed integers is division by a power of two, always rounding down. This is in contrast to the division operator /, which rounds towards zero. I've used >> on a microcontroller, both because it is faster, and because it avoids the discontinuity at zero. Yes, I checked the compiler manual that the implementation defined it in the way I expected. – Depurate

arithmetic shift is very common when used to "spread" the sign bits, you can find lots of examples here – Southwards

Answer 1

Perhaps the best known is the branchless absolute value:

int m = x >> 31;
int abs = x + m ^ m;

Which uses an arithmetic shift to copy the signbit to all bits. Most uses of arithmetic shift that I've encountered were of that form. Of course an arithmetic shift is not required for this, you could replace all occurrences of x >> 31 (where x is an int) by -(x >>> 31).

The value 31 comes from the size of int in bits, which is 32 by definition in Java. So shifting right by 31 shifts out all bits except the signbit, which (since it's an arithmetic shift) is copied to those 31 bits, leaving a copy of the signbit in every position.

Nocuous

Although the arithmetic shift is not necessary here (as you state yourself), this is the first answer that does answer my question, thank you! – Vaasta

+1 for a real example. +0.5 because it is creative. -0.5 for premature optimization (almost every compiler should optimize a call to abs into a branchless instruction, probably even faster than this handcrafted version; do not try to be smarter than your compiler unless you know you are) – Fogy

Answer 2

It has come in handy for me before, in the creation of masks that were then used in '&' or '|' operators when manipulating bit fields, either for bitwise data packing or bitwise graphics.

I don't have a handy code sample, but I do recall using that technique many years ago in black-and-white graphics to zoom in (by extending a bit, either 1 or 0). For a 3x zoom, '0' would become '000' and '1' would become '111' without having to know the initial value of the bit. The bit to be expanded would be placed in the high order position, then an arithmetic right shift would extend it, regardless of whether it was 0 or 1. A logical shift, either left or right, always brings in zeros to fill vacated bit positions. In this case the sign bit was the key to the solution.

Jerky

Can you give an example, please. – Vaasta

I don't have a handy code sample, but I do recall using that technique many years ago in black-and-white graphics to zoom in (by extending a bit, either 1 or 0). For a 3x zoom, '0' would become '000' and '1' would become '111' without having to know the initial value of the bit. – Jerky

You describe a situation in which you want to have logical bit-shifting, not as arithmetic bit-shifting. In this case you should simply use unsigned integers to avoid the problem with the sign. – Fogy

No, this was explicit arithmetic shift. The bit to be expanded would be placed in the high order position, then an arithmetic right shift would extend it, regardless of whether it was 0 or 1. A logical shift, either left or right, always brings in zeros to fill vacated bit positions. In this case the sign bit was the key to the solution. – Jerky

Answer 3

Here's an example of a function that will find the least power of two greater than or equal to the input. There are other solutions to this problem that are probably faster, namly any hardware oriented solution or just a series of right shifts and ORs. This solution uses arithmetic shift to perform a binary search.

unsigned ClosestPowerOfTwo(unsigned num) {
  int mask = 0xFFFF0000;
  mask = (num & mask) ? (mask << 8) :  (mask >> 8);
  mask = (num & mask) ? (mask << 4) :  (mask >> 4);
  mask = (num & mask) ? (mask << 2) :  (mask >> 2);
  mask = (num & mask) ? (mask << 1) :  (mask >> 1);
  mask = (num & mask) ?  mask       :  (mask >> 1);
  return (num & mask) ? -mask       : -(mask << 1);
}

Evelyn

Answer 4

Indeed logical right shift is much more commonly used. However there are many operations that require an arithmetic shift (or are solved much more elegantly with an arithmetic shift)

• Sign extension:

  • Most of the time you only deal with the available types in C and the compiler will automatically sign extend when casting/promoting a narrower type to a wider one (like short to int) so you may not notice it, but under the hood a left-then-right shift is used if the architecture doesn't have an instruction for sign extension. For "odd" number of bits you'll have to do the sign extension manually so this would be much more common. For example if a 10-bit pixel or ADC value is read into the top bits of a 16-bit register: value >> 6 will move the bits to the lower 10 bit positions and sign extend to preserve the value. If they're read into the low 10 bits with the top 6 bits being zero you'll use value << 6 >> 6 to sign extend the value to work with it
  • You also need signed extension when working with signed bit fields

    struct bitfield {
        int x: 15;
        int y: 12;
        int z: 5;
    };
    
    int f(bitfield b) {
        return (b.x/8 + b.y/5) * b.z;
    }
    

    Demo on Godbolt. The shifts are generated by the compiler but usually you don't use bitfields (as they're not portable) and operate on raw integer values instead so you'll need to do arithmetic shifts yourself to extract the fields
  • Another example: sign-extend a pointer to make a canonical address in x86-64. This is used to store additional data in the pointer: char* pointer = (char*)((intptr_t)address << 16 >> 16). You can think of this as a 48-bit bitfield at the bottom
  • V8 engine's SMI optimization stores the value in the top 31 bits so it needs a right shift to restore the signed integer

• Round signed division properly when converting to a multiplication, for example x/12 will be optimized to x*43691 >> 19 with some additional rounding. Of course you'll never do this in normal scalar code because the compiler already does this for you but sometimes you may need to vectorize the code or make some related libraries then you'll need to calculate the rounding yourself with arithmetic shift. You can see how compilers round the division results in the output assembly for bitfield above

• Saturated shift or shifts larger than bit width, i.e. the value becomes zero when the shift count >= bit width

  uint32_t lsh_saturated(uint32_t x, int32_t n) // returns 0 if n == 32
  {
      return (x << (n & 0x1F)) & ((n-32) >> 5);
  }
  
  uint32_t lsh(uint32_t x, int32_t n) // returns 0 if n >= 32
  {
      return (x << (n & 0x1F)) & ((n-32) >> 31);
  }
  

• Bit mask, useful in various cases like branchless selection (i.e. muxer). You can see lots of ways to conditionally do something on the famous bithacks page. Most of them are done by generating a mask of all ones or all zeros. The mask is usually calculated by propagating the sign bit of a subtraction like this (x - y) >> 31 (for 32-bit ints). Of course it can be changed to -(unsigned(x - y) >> 31) but that requires 2's complement and needs more operations. Here's the way to get the min and max of two integers without branching:

  min = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
  max = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
  

  Another example is m = m & -((signed)(m - d) >> s); in Compute modulus division by (1 << s) - 1 in parallel without a division operator

Southwards

Answer 5

I am not too sure what you mean. BUt i'm going to speculate that you want to use the bit shift as an arithmetic function. One interesting thing i have seen is this property of binary numbers.

int n = 4;
int k = 1;

n = n << k; // is the same as n = n * 2^k
//now n = (4 * 2) i.e. 8
n = n >> k; // is the same as n = n / 2^k
//now n = (8 / 2) i.e. 4

hope that helps.

But yes you want to be careful of negative numbers i would mask and then turn it back accordingly

Rashad

"But yes you want to be careful of negative numbers i would mask and then turn it back accordingly" Negative numbers is where arithmetic right shift makes a difference to logical right shift. For positive numbers arithmetic rightshift == logical right shift, so you could as well use >>> (in Java). I was explicitly looking for cases where "the number could be negative". – Vaasta

In java i can assume there in an abstraction. I dont know of a <<< or >>> in c or c++. But if you try my example with a negative. you get what you expect. -4 << 2 = -16 just as 4 << 2 = 16. Though it makes no sense to me logically. it seems to be the answer i get. So what i meant by masking is. I have used x << 2^x to square numbers but then i always mask it to be a positive number. because my intent is to square. – Rashad

No, there aint no such operator. But still, I am referring to cases where the left operand could be negative. As long as it is always positive everything is fine. In addition,I am talking about right shift. Yes, -4 << 2 =-16, but here is a counter example: -1>>1 = -1 not 0! – Vaasta

That is interesting, never came across that before. – Rashad

@gexicide: I don't see a difference between 9 >> 1 = 4 and -9 >> 1 = -5. Shifting right by 1 discards one bit, always; and so it always rounds down. – Languet

@Jongware: True. But I don't see a real application for this behaviour. If there was one, I would love to read about it in an answer. The problem with this semantics is you no longer have a>>1==a/2, so you cannot use shifting as a real substitute for the division operator anymore. And I do think that 99% of all programmers are not aware of that fact. Usually, rounding towards zero is what you want (and expect!) when performing an integer division. – Vaasta

Note that for readability reasons this kind of arithmetic operation is not recommended in real code. To express that you want to divide, use the / operator! Even if you divide by a power of two of which you only have the exponent in a variable: n = n / (1 << k) is easier to read than n = n << k (at least IMHO). Note that it's probably optimized to a bit-shifting operation by the compiler if that operation is going to be faster and if the results are the same. Writing n << k for optimization reasons is premature optimization, which is bad. – Fogy

@leemes: So we have yet another use case where arithmetic shift (or rather any shift) should not be used. :) – Vaasta

@Vaasta Well, maybe you as the programmer should not use it, but the compiler will use it if it is faster. I guess that makes most sense. Since arithmetic bit-shifting is, in my opinion, just a bad way of dividing / multiplying by a power of two. – Fogy

Answer 6

In C when writing device drivers, bit shift operators are used extensively since bits are used as switches that need to be turned on and off. Bit shift allow one to easily and correctly target the right switch.

Many hashing and cryptographic functions make use of bit shift. Take a look at Mercenne Twister.

Lastly, it is sometimes useful to use bitfields to contain state information. Bit manipulation functions including bit shift are useful for these things.

Bunnybunow

My question is about arithmetic bit shifts where the left operand can be negative. This question is not about usual shifting of positive or unsigned numbers. – Vaasta