In Java because (250 >> 4) is more optimized than (250 / 16)

Question

I’m taking a Java course and in a class the teacher said that this code:

int xstart = Camera.x >> 4;
int ystart = Camera.y >> 4;

is more "fast or optimized" than this code:

int xstart = Camera.x/16;
int ystart = Camera.y/16;

but he didn’t say why or how >> is called. I would like to know what this operator does as it is called and why it is more optimized.

Answer 1

Have you tested? Someone talk and be true will a big difference.

I’m not going to say and I don’t have an environment right now that I can do a proper test to show whether this is really true or not. And I’m not going to waste my time because I can tell you that language says nothing about it.

It may be that some implementation of the language, perhaps even the most used by all, may be like this, or it may not, at least in this example.

Some languages have the philosophy to execute as quickly as possible and will tend to perform optimizations where you find some situation that the compiler or Jitter can. Java is a language that tends to do this, and I would find it odd if it didn’t.

The division is one of the slowest single operations a processor can make and has several ways to optimize it and trade it in for other ways. Some compilers (in C/C++, Fortran, etc.) even make optimizations in "broken" numbers. Those that do not in any numbers at least do in numbers that are power of 2, which is the case of 16 (2 to 4), since the computer is all binary.

If it were a variable there in the divider it would be more complicated because then he would not know whether or not to do the optimization until the moment of execution. In some cases the Jitter could benefit from this, but only in specific or extreme scenarios would get the gain.

So there’s a good chance that’s not true. Compiler/Jitter can work for you to make your code more readable and perform best at the same time.

If this does not actually occur, if you have tested, correctly, and realized that in fact optimization does not occur, and this optimization is important within the context (Today gaining on access to memory is much more important than reducing processing cycles, it may be that an optimization there only makes a part go faster to fall into congestion before and get stuck there), if all the indications are important and the readability is not so important then exchange the division operator for the bit shift (specifically the shift to right) in your code can give an interesting gain.

In no way am I saying that this micro optimization in the code should not be done. Your teacher may have measured and since the most common is that Java does not currently perform this optimization, just keep in mind that this may not be true in all Java implementations and at any time. This may change next month, it may have changed last month and no one has noticed it yet, or it may be until in some more specific situation the optimization occurs.

More on the subject have already been answered in other languages and works the same, so I will not explain again:

• What are the operators for | & << >>?
• What is the function of operators <<, >> and >>> in Javascript
• How bit operators work?
• Doubt on how to use Shift in Java
• How to convert an int to two bytes in C/C++?
• What << in PHP means?
• Logic of these bit-by-bit operations

These operators only move bits to one side, which is very simple and fast. It would be more or less you instead of doing a whole division calculation for 10 just using the little rule of taking the right digits, a lot faster than doing all those traditional division accounts, right? If you know that the divider is a base power 10 can use this trick, and this is the same as the bit shift does to replace division or multiplication (which gain is large but not as large as division) in base powers 2. When the processor does the splitting it has to process in a more complicated way, as we do when the splitter is complicated in base 10 as well.

So, just as moving 4 digits in decimal you are dividing by 10,000 (or multiply move to the left and fill in with zeros the additional), when it tells you to move 4 binary digits you are dividing by 16, after all 10 to the 4 gives 10,000 and 2 to the 4 gives 16. So if the division were by 32 it would have to move by 5 or if it was 8 it would only move by 3. If the division was by 10 for example, you can’t do that. You can even do two or more operations that would give the same result, and even with 3 or 4 operations should be faster than the division, but the code is much more complicated, you would have to comment because you did it and to be able to do =this in the hand is hard work, and it may be that the hand misses and gets slower, so "nobody" does and leaves to see if the compiler thinks it’s worth it.

The optimization is precisely the compiler/Jitter swap one processor instruction for the other without you interfering. And if it’s not done on its own you need to do.

Few situations are justified, it’s good to know, but not that you should always use. Bit handlers have been created in part for optimization, but the biggest reason is when the semantics of what you want to do is bit displacement and not division. If the most readable is to divide, divide.

Can not use this form in any situation, hkotsubo response gives some details about it. One of the limitations it is not to take care of the sign.

That’s why I always say that to learn you need to know why, as you’re wondering here. When you learn a "good practice", in other words, someone says, "That’s it, believe me" you’re not learning to program, you’re just memorizing a rule you don’t understand. Curiosity to understand the reason is fundamental.

Answer 2

Just to be pedantic and clarify what was said in the comments, the >> is an operator bit shift (in this oracle tutorial the separation between operators is clear bitwise - and (&), or (|), etc - and operators bit shift).

To be more precise, the language specification (which also puts the operators of bitwise and of shift in separate sections, indicating which technique and pedantly speaking the >> is not a bitwise Operator and yes a shift Operator) calls that operator "Signed right shift". And as its name says, it moves bits to the right.

^{Of course if you say you’re a bitwise operator everyone will understand. It’s just my pedantry talking louder...}

For example, the number 38 in binary corresponds to 00100110. If we do 38 >> 4, means that bits should be moved 4 positions to the right. That is:

00100110  <- valor original (38)
00000010  <- deslocando 4 posições para a direita

Note that the last 4 bits (0110) are lost with the offset. And on the left, they are filled with zeros. The result is 00000010, which is equal to number 2 (which is the same result as 38 / 16).

---

And why is it equivalent? ^{_{(with reservations, see more about this at the end)}}

Forget the binary numbers for now. Imagine the numbers in base 10 (those "normal" ones that everyone uses in day-to-day life).

If I have the number 457090, and I want to divide by 1000 (disregarding the rest of the division and the decimals), all I have to do is eliminate the last 3 digits, resulting in 457.

Basically, if I eliminate only 1 digit of the end (45709), it is the same as dividing by 10. If I eliminate 2 digits at the end (4570) is the same as dividing by 100 (or by 10²), if I eliminate 3 digits of the end (457) is the same as divided by 1000 (or by 10³) and so on.

In general, if I delete N digits from the end, it is the same as dividing the number by 10^N. But that’s only true if the number’s on base 10.

Generalizing this rule, if a number is represented in base B and I delete N digits at the end, the result is the same as dividing that number by B^N.

So if the number is in base 2, and I shift 4 positions to the right (which is the same as deleting the last 4 digits), then the result is the same as dividing that number by 2⁴ (that is, the same as dividing by 16).

Whether this will be more optimized or not, the other answer already explained in detail (and the answer is basically, "It depends").

---

But there’s a catch

All this stuff I’ve been talking about is for positive numbers. If the number is negative (and this is indicated by the first bit, which in negative numbers is 1), then it is no longer equivalent. For example, if the number is -38 we will have the following:

int n = -38;
System.out.println(n / 16); // -2
System.out.println(n >> 4); // -3

That’s because bits are like that now:

11111111111111111111111111011010  <- valor original (-38)
11111111111111111111111111111101  <- deslocar 4 posições para a direita (-3)

When moving to the right, the left positions hold the signal. In the case of positive numbers, the first bit is zero, so when scrolling to the right, the left positions are filled with zero. But in negative numbers the first bit is 1, and the signal is kept while doing the right shift (in fact, that’s why the operator is called "Signed rigth shift" - "Signed" indicates that it is "with signal", that is, the signal is taken into account when making the shift).

The result only equals if the division is exact (for example, if it were -32, both would result in -2).

---

Just out of curiosity, there is also a unsigned right shift (>>>), that always fills the left positions with zeros (for positive numbers, will continue to be equivalent to the division, but for negatives will give a completely different result).