3 ms·

the part about right shift not being equivalent to a division by 2 even if sign bits are copied didn't really convince me. -1/2 = -0.5 floor of that is -1. -

the part about right shift not being equivalent to a division by 2 even if sign bits are copied didn't really convince me. -1/2 = -0.5 floor of that is -1. -1 >> 1 == -1 What's the issue? It's integers. The floor is implied.

wahern 2y ago
Integer division rounds to 0, not negative infinity. -1 / 2 == 0, or -0 if you're lucky enough to have the hardware. For ones' complement and signed magnitude, though, right shift of a negative number also rounds to 0, I think.
adrian_b 2y ago
As another poster has already said, the floor is not implied. Right shift is equivalent with division if integer division were defined in a way consistent with two's complement number encoding. Alas, that is not true. The integer division instructions of most CPUs have definitions that are inherited from extremely ancient computers that used sign-magnitude number encoding and they truncate the quotient towards zero. There are many possible definitions of integer division and this is one of the worst, by failing to have many of the desirable mathematical properties (for instance it partitions the integer numbers into equivalence classes that have different sizes, which is bad for something like a histogram). The C language just inherits the bad integer division definition implemented in hardware, instead of using a better definition that would result in lower performance due to additional overhead. Therefore it ends with two different kinds of integer divisions, one for "/" and another for ">>", which coincide for non-negative numbers, but which differ for negative numbers. In my opinion this is a mistake that exists in almost all programming languages. They should have used a better definition for the integer division and remainder operations than the one implemented in hardware. The use of integer division with negative numbers happens only seldom, so its performance is unlikely to be important, but giving more useful and consistent results can simplify some programs and avoid surprising bugs. Now it has become a chicken and egg problem. The CPU hardware continues to implement the bad definition, because that is what the popular programming languages expect, while the programming languages continue to use the bad definition because it is implemented in hardware. See "The Euclidean definition of the functions div and mod": https://dl.acm.org/doi/10.1145/128861.128862 https://dl.acm.org/doi/10.1145/128861.128862

wahern 2y ago

Integer division rounds to 0, not negative infinity. -1 / 2 == 0, or -0 if you're lucky enough to have the hardware. For ones' complement and signed magnitude, though, right shift of a negative number also rounds to 0, I think.

adrian_b 2y ago

As another poster has already said, the floor is not implied. Right shift is equivalent with division if integer division were defined in a way consistent with two's complement number encoding. Alas, that is not true. The integer division instructions of most CPUs have definitions that are inherited from extremely ancient computers that used sign-magnitude number encoding and they truncate the quotient towards zero. There are many possible definitions of integer division and this is one of the worst, by failing to have many of the desirable mathematical properties (for instance it partitions the integer numbers into equivalence classes that have different sizes, which is bad for something like a histogram). The C language just inherits the bad integer division definition implemented in hardware, instead of using a better definition that would result in lower performance due to additional overhead. Therefore it ends with two different kinds of integer divisions, one for "/" and another for ">>", which coincide for non-negative numbers, but which differ for negative numbers. In my opinion this is a mistake that exists in almost all programming languages. They should have used a better definition for the integer division and remainder operations than the one implemented in hardware. The use of integer division with negative numbers happens only seldom, so its performance is unlikely to be important, but giving more useful and consistent results can simplify some programs and avoid surprising bugs. Now it has become a chicken and egg problem. The CPU hardware continues to implement the bad definition, because that is what the popular programming languages expect, while the programming languages continue to use the bad definition because it is implemented in hardware. See "The Euclidean definition of the functions div and mod": https://dl.acm.org/doi/10.1145/128861.128862 https://dl.acm.org/doi/10.1145/128861.128862