I'd consider the former as an "overflow" (shift on a signed type affecting the MSB)
a bitshift is not the same as a multiplication by two. It is literally moving all the bits. If a left shift that gives you a negative overflows, a rightshift with a negative would also need to overflow. I think we can assume that anyone using a bitshift operation did not mean to create a manual optimization for a multiplication/division by a power of 2. Because that optimization is the compiler's duty, not the programmer's.
With shifts you are in bit twiddling territory – the semantics are well-known (including truncation of any bits shifted out). Checking for overflow on shifts would be more complex than with addition, because there's no CPU support.
bitshift x << s has a debug overflow check for the error where s is larger or equal to the number of bits in x.
The carry flag is set if the shift results in a one being shifted out on most of the CPUs I have programmed, including 6502, z80, mc680x0, and x86. I don't think the Sparc and Alpha used the carry bit, so its probably something you cannot rely on across all CPUs.
I would also say that in the algebra of binary rings, a shift left is a multiplication by 2, and a shift right is a division by 2. It is a fundamental property that shift left gives the same result as multiply by 2, and shift right gives the same result as divide by 2, of a similar nature to that relating addition to multiplication (that multiplication is repeated addition). It is the same as multiplying by 10 in decimal adds a zero, it comes from the fundamental nature of numeric notation where we write numbers in columns of increasing powers of 10 from right to left, (or powers of 2 in binary). I am aware that there are some notations like Roman numerals that do not allow this, but the Roman's didn't have a zero either. Some properties of prime numbers have been shown to hold in all number bases, suggesting there is something fundamental about the representation of numbers as digits of increasing powers of a base.
Although implementing multiplication by 2 as adding a value to itself can be seen as a optimisation, we would not expect to get different answers. Another point of view is that if it does not give exactly the same answer then it is not actually an optimisation but an error.
1 Like
Again, if you do want an overflow check, you can use a.checked_add(a), or use a + a and either enable debug_asserts on release or live with the fact that your release binary has no check.
Yes, shifting will conditionally set the carry flag on many architectures. But note that shifting can be done by higher values than one, so special casing goes far over the border into bit twiddling country.
I personally view bitshift and multiplication as different operations that usually happen to have same results because of underlying math. Similar results does not mean we're free to treat it as the same operation.
User (programmer) is expected to use correct primitives for operations. If he decides to use bitshift, it's safe to say he is interested in bitshift itself, not affiliated multiplication-like properties (because then he would use multiplication primitive). Silent overflow is a desired outcome in this case (that's basically a part of bitshift definition).
If for any reason programmer uses bitshift for multiplication (e.g. manual optimization), he should be responsible for "translating" bitshift primitive into multiplication primitive, which in this case means manually handling overflow edge cases.
So I could reasonably say (substituting other operations):
I personally view repeated-addition and multiplication as different operations that usually happen to have the same results because of underlying math...
The fact is they always have the same result because of the algebra of boolean rings.
Its is a shame the CPU does not set the overflow flag if 'any-ones' get shifted out, really I would class this as an error in the CPU design as it does not respect the equivalences of operations properly. I think the x86 sets the overflow flag on single bit arithmetic-left shifts, but not for multi-bit shifts, which seems a bit inconsistent to me.
If you multiply two 32 bit numbers the potential result is 64 bits, and really that should be reflected in the type signature of the multiply. Most CPUs generate both high and low words of the result, but most high level languages throw half of this away. Looking at it in this way if you want to shift a 32bit value left to multiply it, shifting left between 1 and 32 bits, you should first sign extend it to 64bits and then shift. This is not really much bit twiddling at all just: (x as i64) << y
Runtime overflow checking is a bit useless really, by the time the software is in the hands of the user, an 'overflow' failure is going to cause problems. Static range checking seems a better option, and that can generate warnings if arithmetic operations have the potential to overflow, by tracking the min and max values of ranges after each operation. I think if you are really concerned about overflow errors then you should be using proper integers like BigInt.
Yeah I even spotted a typo in the relevant RFC. But it isn't directly related to my point.
Don't do bit twiddling with a signed int.
Yet CPUs have thrived with this "error" for many decades. I have personally written tens of thousands of lines of x86 assembly and never cared about overflows on bit shifts (also if I needed something like this, I'd use a rotating shift and mask, which would set the equal flag if something was masked out).
Note that LLVM is free to elide the zero extension on multiplies, so (a as u64) * (b as u64) should compile to a single mul on x86.
Also we do have some lints in clippy, and a number of issues outlining more. We may even one day get something similar to what you proposed.
Unless you really know what you're doing. Which you should anyway when twiddling bits.
For example, if you want arithmetic right-shift in Rust, you need to use signed ints.
Here's a nice video of Stepanov Elements of Programming - YouTube watch from 16:35 for the start of the slide and 18:59 if you want to skip straight to the relevant part. The summary if you do not have time to watch is "We like bits", but Stepanov puts it much better than I could.
In secion 3.4 of "Elements of Programming" Stepanov states that special case procedures that are more efficient belong in the basis of the type. Stepanov includes "binary_scale_up_nonnegative" and "binary_scale_down_nonnegative" in the basis functions of the Integer "concept" (which would be a trait in Rust), but it is interesting to note he does not include logic operations like and, or and not. The list of special case procedures that "any integer type must provide" if you are interested are: successor, predecessor, twice, half_nonnegative, binary_scale_down_nonnegative, binary_scale_up_nonnegative, positive, negative, zero, one, even, odd, that is in addition to the standard operators for sum, difference, product, quotient, remainder, and literal constructors.
Repeated addition always has the same result, there are no exceptions - so it's safe to view it as the same operation.
The same is true of the shift operation, it always gives the same result as multiply or divide by 2. However some implementations of shift appear to incompletely implement the operation, not correctly setting flag bits etc. Overflowing a shift register by shifting left is as much an overflow as overflowing an adder.
If we talk about the theoretical shift operation on an abstract bit vector, then shift left is always the same as multiply by 2 and shift right (logical or arithmetic as appropriate) the same as divide by 2. A high level language should isolate the programmer from the details of the hardware implementation, IE it should provide programming to n-bit binary rings. C has an abstract model where it ignores overflows, so it correctly preserves the identity between shift and multiply. The other choice is to flag an overflow on all operations where appropriate. To flag some and not others seems inconsistent at best as it does not preserve the identity.
I think that is the critical point, the correctness of a model is determined by the preservation of the identities. In this case the model of n-bit binary rings is broken because it does not correctly preserve the identity between shift and multiply/divide by 2. It is the identity that is fundamental, the model is just a model.