Unsigned right shift operator in Swift?

[phhnguyen]

I have been coding my chess app in Swift and want to implement a random function with a code modified from Java one. That function uses some unsigned right shift operators (>>>) and I don't know how to implement it correctly in Swift.

My function works mainly with long (Int64) and speed is not a big problem.

Sorry for being lazy to do it myself and thanks in advance for any helps!

The unsigned right shift operator is defined from Java doc as the following:

Code: Select all

The value of n >>> s is n right-shifted s bit positions with zero-extension, where:
- If n is positive, then the result is the same as that of n >> s.
- If n is negative and the type of the left-hand operand is int, then the result is equal to that of the expression (n >> s) + (2 << ~s).
- If n is negative and the type of the left-hand operand is long, then the result is equal to that of the expression (n >> s) + (2L << ~s).

The added term (2 << ~s) or (2L << ~s) cancels out the propagated sign bit.

[Dann Corbit]

This is going to sound stupid, but why not just divide by powers of 2 in a table?

If the optimizer is any good, it will turn the operations into shifts anyway.

[jwes]

Dividing by powers of 2 is equivalent to signed right shift.

[hgm]

Just define an array mask[63], which you initialize as

Code: Select all

mask[63] = 1;
for(i=62; i>= 0; i--) mask[i] = 2*mask[i+1] + 1;

Then everywhere you need k >>> n, do

Code: Select all

(k >> n) & mask[n]

(This assumes Swift has a bitwise AND operation.)

If that is not the case, you can replace x = k>>>n by

Code: Select all

if(n > 0) {
  x = k>>1;
  if(x < 0) x -= 1<<63;
  x >>= n-1;
} else x = k;

[phhnguyen]

Thanks a lot Muller and all other people!

Both ways can be coded in Swift. I prefer to the first one (using mask).

[mar]

Dividing by powers of 2 is equivalent to signed right shift.

Sorry but this is not true (assuming 2's complement representation):
-1 >> 1 = -1
-1 / 2 = 0
signed shift right can be thought of as rounding towards -infinity, say you have a fixed point number x with n bits fractional part. this is nice as it allows trivial rounding towards nearest integer:
ix = (x + (1 << (n-1)) >> n

I have another obvious table-free version for doing unsigned logical shift right (untested) but I doubt it'd be competitive with hgm's solution in terms of performance:

Code: Select all

(k >> n) ^ ( (k & 0x8000000000000000ll) >> n ) * 2

(assuming * has higher precedence than xor and that *2 will be optimized to either shift or addition)

Alternatively one could omit *2 and instead do second >> by n-1, but this won't work for cases where n is zero

EDIT: since I assume this is for bitboards, it's very likely that MSBit will be zero in most cases, so perhaps doing a special case for k >= 0 might help (if you can tell the compiler that's the likely case to happen).