Apparent arithmetic bug

This is the original line of code that works.

*seg.get_unchecked_mut((kn - 1) >> S) |= !(((2 as MWord) << ((kn - 1) & BMASK)) - 1);

(kn - 1) & BMASK will be a number from 0 - 63.
(2 as MWORD) is the same here as 2u64.
So, it performs (for u64 sized values) the equivalent of: (2 << {0..63}).
Then I invert all 64 bits, and subtract 1, so I end up with 00001000..0 => 1111000..00000.
So I'm setting all the bits higher than the number of bits for (kn - 1) & BMASK to 1.

Below are code equivalents that fail in Rust, but work in other languages, like Crystal.

*seg.get_unchecked_mut((kn - 1) >> S) |= !0u64 << (((kn - 1) & BMASK) + 1)

*seg.get_unchecked_mut((kn - 1) >> S) |= 0xffffffffffffffff << (((kn - 1) & BMASK) + 1)

The only way I've been able to make it work correctly is with the code below.

*seg.get_unchecked_mut((kn - 1) >> S) |= (!0u64 << ((kn - 1) & BMASK)) << 1

So it seems the !0u64 << shiftbits is off by one shift, and doing an extra one makes it work.

This makes no sense and surely must be a bug, or something else completely nonintuitive is going on.

This is a bit messy and hard to follow. Can you make an example on the playground that compiles and shows the issue?

What do you expect !0_u64 << 2 to do? currently this will be all ones except the 2 least significant bits.

assert_eq!(!0_u64 << 2, !0_u64 & !0b11)

Those are equivalent in Rust (are you sure that you don't have a buffer overflow with that get_unchecked_mut?)

Note: you have used a different bitshift between all 3 examples

1 Like

Running this code on:
indicates it doesn't like doing a 64 bit shift (when kn is multiple of 64) for x and z,
but x works in the code while z is one shift off.

fn main() {
    const BMASK: usize = 63;
    let kn = 63;
    //let x = !((2u64 << ((kn - 1) & BMASK)) - 1);  // this works in code
    //let y = (!0u64 << ((kn - 1) & BMASK)) << 1;   // this works in code
    let z =  !0u64 << (((kn - 1) & BMASK) + 1);   // this doesn't work in code
    //println!("x = {}", x);
    //println!("y = {}", y);
    println!("z = {}", z);

Doing a 64-bit left shift on 64-bit number should return 0, but this is flagged as an error here, for the z case but not for the x case in the code (no errors are raised at compiletime in my code).

You aren't bitshifting by 64, you are bitshifting by 63, i.e. (((kn - 1) & BMASK) + 1) == 63. All three x, y, and z are identical.

Change the values of kn to see the differences. When kn = 64 z bombs on the playground, but in the code it is one shift off.

I would expect a left shift modulo 64 should return 0.

Ahh, I see the issue now. You are seeing a different overflow behavior from Rust compared to Crystal. You can get around this with x.checked_shl(bitshift).unwrap_or(0)

1 Like

What is x in your example? Can you translate the code to use your example correctly.

(!0u64).checked_shl(((kn - 1) & BMASK) + 1).unwrap_or(0)

I think you mean checked_shl rather than overflowing_shl.

1 Like

Yeah, anyway the issue is that the number of bits you shift will wrap around once you reach 64 bits, so you have to handle it separately if you want zero in that case.

For comparison, Crystal used to have undefined behavior for shifting by too many bits, but changed it to always return 0.

In Rust, the shift distance is masked so that 1u64 << n is equivalent to 1u64 << (n % 64).

JavaScript works the same as Rust (and also converts the LHS to a signed 32-bit number first).

C# also works like Rust, and so does Java.

In Swift, the << operator works like Crystal, while the &<< operator works like Rust.

In C and C++, of course, this is still undefined behavior.


In the playground this run but gives 0 for kn = 64, but when I run it in my code it works correctly.
It doesn't make me feel I know what to expect in general for this.

let z = (!0u64).checked_shl( (((kn - 1) & BMASK) + 1) as u32 ).unwrap_or(0);

*seg.get_unchecked_mut((kn - 1) >> S) |= (!0u64).checked_shl( (((kn - 1) & BMASK) + 1) as u32 ).unwrap_or(0);

Bitshifts with too many bits have always had inconsistent behaviour between all sorts of languages.

Mathematically it should not be an error to shift a 64-bit number 64 bits, as all that should do is clear the register (put 0s in all bits). If you can't do this you will inherently not be able to clear all the bits and will introduce systematic math errors.

If this behavior isn't allowed in Rust ( left or right shifts) I would consider that a bug in the shift operators and unexpected behavior. This code works correctly in every other language I've used (I obviously haven't used every existing language there is) so from experience it has been standard behavior.

The problem is that common CPU architectures provide direct support for the "masked shift" operation, but not for the "checked shift" operation. This means that "masked shift" can compile to a single instruction, while the checked version requires multiple instructions or even a branch.

Rust, C#, Swift, JavaScript, and Java all provide "masked shift" because they don't want to slow down every single shift just in case some of them are shifting by too many bits. (Most of these languages also provide alternatives with different semantics.)


Relying on overflow behavior is always a bad idea, if you have specific needs you need to state them explicitly. In this case you want overflow to be set to 0, so you need to use a.checked_*(b).unwrap(default), if you know your overflow requirements follow one of wrapping_* or saturating_*, then you could use one of those.

On a seperate note: I think Rust could provide a saturating_shl and saturating_shr that set to 0 on overflow rather than wrapping.

In my case I wouldn't call what I'm not doing overflow shifting. I only perform shifts of 1 - 64 bits, not greater than 64 bits. If the lsb is '1' and the most you can left-shift it is 63 bits (to only get 0x8000000000000000) you would have to do allot of mathematical manipulations to account for that deficiency.

Yes! :+1:

Shifting a 64-bit value by 64 bits is overflow exactly because shifting by 64 bits moves the 1 off the end least significant bit off of the end.

edit for clarity

You're always moving bits off the end, that's why you're shifting them, you don't want them.
But I won't quibble over terminology, we understand the point.