Does Julia has bitwise circular shift?

This documentation page lists the logical and arithmetic shift, as well as the bitwise NOT, AND, OR and XOR. However, the circular shift is absent.

Does Julia has a bitwise circular shift? If yes, where can I find it’s documentation? If not, is it possible to implement it with performance similar to the other bitwise operations?

I don’t think it exists, but for Int64 this should work and be about 3x slower than other bitshifts (since it uses 3 of them). You could easily enough write methods for other types of Integer, but I don’t know of a way in Julia to automatically get the number of bits in an integer.

function circshift(x, n)
    return (x<<n) | (x>>(muladd(8, sizeof(x), -n)
end

EDIT: now should work for any Integer subtype

1 Like

sizeof(x) or sizeof(typeof(x)) gives the amount of bytes

1 Like

Hot off the press: bitrotate

https://docs.julialang.org/en/v1.5/base/math/#Base.bitrotate

help?> bitrotate
search: bitrotate

  bitrotate(x::Base.BitInteger, k::Integer)

  bitrotate(x, k) implements bitwise rotation. It returns the value of x with its bits rotated left k times. A negative value of k will rotate to the right instead.

  │ Julia 1.5
  │
  │  This function requires Julia 1.5 or later.

  julia> bitrotate(UInt8(114), 2)
  0xc9

  julia> bitstring(bitrotate(0b01110010, 2))
  "11001001"

  julia> bitstring(bitrotate(0b01110010, -2))
  "10011100"

  julia> bitstring(bitrotate(0b01110010, 8))
  "01110010"
11 Likes
(x << ((sizeof(T) << 3 - 1) & k)) | (x >>> ((sizeof(T) << 3 - 1) & -k))

is the body of the method. The biggest difference is that this actually can rotate in both directions as opposed to mine which was unidirectional.

1 Like

It came right when I need :grinning:, it’s timing couldn’t be better!

Actually, it appears to be just as fast as an ordinary bitshift. It seems that the compiler is smart enough to optimize it into a single bitrotate operation (from https://en.wikipedia.org/wiki/Circular_shift):

Unfortunately, many programming languages, including C, do not have operators or standard functions for circular shifting, even though virtually all processors have bitwise operation instructions for it […] some constructs in standard ANSI C code may be optimized by a compiler to the “rotate” assembly language instruction

3 Likes